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. -- http://mail.python.org/mailman/listinfo/python-list
