On Thu, Nov 29, 2001 at 03:22:42PM -0500, Uri Guttman wrote: > >>>>> "MGS" == Michael G Schwern <[EMAIL PROTECTED]> writes: > MGS> A Crash Course On BigO Notation As Presented By A Guy Who Failed > MGS> Fundamental Data Structures And Algorithms 1 * > > MGS> O(1) means it runs in a fixed amount of time regardless of how much > MGS> data is to be processed. A hash is an O(1) algorithm. > > actually given linear searches in buckets, most hashes are not truely > O(1) but close enough.
Given a "perfect" hash algorithm which evenly distributes the data over all buckets it is. Of course, there is no such thing. Even so, most hash algorithms reorder the buckets as they grow to avoid the worst of the collisions, but that reordering is O(n), so you're right. > but as the data set grows its runtime will grow N**2 and that will > eventually be much slower than any typical O(Log N) sort. s/O(Log N)/O(N Log N)/g -- Michael G. Schwern <[EMAIL PROTECTED]> http://www.pobox.com/~schwern/ Perl Quality Assurance <[EMAIL PROTECTED]> Kwalitee Is Job One Plus I remember being impressed with Ada because you could write an infinite loop without a faked up condition. The idea being that in Ada the typical infinite loop would be normally be terminated by detonation. -- Larry Wall in <[EMAIL PROTECTED]>
