Comparing lists - somewhat OT, but still ...

[Steven D'Aprano]

On Sun, 16 Oct 2005 14:07:37 -0700, Paul Rubin wrote:

> 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:


Yes, that is a very good point, and I suppose if a hostile user wanted to
deliberately construct a data set that showed off your algorithm to its
worst behaviour, they might do so. But if you are unlikely to discover
this worst case behaviour by experimentation, you are equally unlikely to
discover it in day to day usage. Most algorithms have "worst case"
behaviour significantly slower than their best case or average case, and
are still perfectly useful.


-- 
Steven.