On Mon, Dec 03, 2001 at 12:09:49PM +0100, [EMAIL PROTECTED] wrote: > > A Crash Course On BigO Notation As Presented By A Guy Who Failed > > Fundamental Data Structures And Algorithms 1 * > > > > O(1) means it runs in a fixed amount of time regardless of how much > > data is to be processed. A hash is an O(1) algorithm. > > Eh, no. A hash gives you O(1) *expected* search/update time, if you've > found an appropriate hash function.
True. Array element lookup is a better example. > > O(logn) means as you increase the amount of data, the time required > > will increase logarithmicly. In order to double the run time > > you have to exponentially increase the data. > > No, it doesn't mean the time increases logarithmically. It means the time > will increase *at most* logarithmically. A significant difference. > > Here's a more precise definition: > > f(n) = O(g(n)) if and only if there are N > 0 and c > 0, such > that for all n > N, |f(n)| < |c * g(n)|. "Crash Course" usually means you try to avoid those sort of precise yet incomprehensible definitions. -- Michael G. Schwern <[EMAIL PROTECTED]> http://www.pobox.com/~schwern/ Perl Quality Assurance <[EMAIL PROTECTED]> Kwalitee Is Job One You see, in this world there's two kinds of people. Those with loaded guns, and those who dig. Dig. -- Blonde, "The Good, The Bad And The Ugly"
