Comparing lists - somewhat OT, but still ...

[Paul Rubin]

Ognen Duzlevski <maketo at norge.freeshell.org> writes:
> > Optimizations have a tendency to make a complete mess of Big O
> > calculations, usually for the better. How does this support your
> > theory that Big O is a reliable predictor of program speed?
> 
> There are many things that you cannot predict, however if the
> compiler was sufficiently documented and you had the knowledge of
> the abovementioned peculiarity/optimization, you could take it into
> account. Bear in mind that the example was given to show a problem
> with a purely experimental approach - it tends to show a tree and
> ignore the forest.  Sometimes this tree can be respresentative of a
> forest but many times it might not be.

Consider the claim that earlier in the thread that adding to a hash
table is approximately O(1):

[Stephen D'Aprano]
> And knowing that hash tables are O(1) will not tell you that, will it?
>
> There is only one practical way of telling: do the experiment. Keep
> loading up that hash table until you start getting lots of collisions.

The complexity of hashing depends intricately on the the data and if
the data is carefully constructed by someone with detailed knowledge
of the hash implementation, it may be as bad as O(n) rather than O(1)
or O(sqrt(n)) or anything like that.  Experimentation in the normal
will not discover something like that.  You have to actually
understand what's going on.  See for example:

http://www.cs.rice.edu/~scrosby/hash/