in reply to Re: A short meditation about hash search performance in thread A short meditation about hash search performance
Man you were so hard, I think he meant the functions behind the algorithms responded to O(log2(n)) asymptotic performance. The big o notation has many uses in other fields but in computing is used with its basic meaning, that's to remark the asymptotic character of the expression enclosed for the function being referred.
Man it seemed you were dying to get the book out of the shelf and spit out some theoretical speech. I think you got the point first time, didn't you?
Peace
Re^3: A short meditation about hash search performance
by tilly (Archbishop) on Sep 12, 2007 at 01:09 UTC

There are so many things to respond to here that I have no idea where to begin. So I'll list them randomly:
 Where do you get the O(log2(n)) from? With a flat memory model, hashing algorithms are not O(log2(n)).
 Reread my post and you'll see that I explicitly acknowledge the fact that hackers do not exactly use bigO notation in the way that Knuth did. Why do you think that he said otherwise?
 Reread the root post and you'll discover that pg both misunderstood bigO notation as used by Knuth, and as used by hackers. As far as most people are concerned, a hash lookup is O(1). That he thought otherwise was due to a misunderstanding on his part about what bigO notation means.
 Reread the root post and you'll find lots of incorrect attempted pedantry. When someone tries to get pedantic, I think it is fair and reasonable to be pedantic back.
 [reply] 
