Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re^3: A short meditation about hash search performance

by tilly (Archbishop)
on Sep 12, 2007 at 01:09 UTC ( #638467=note: print w/ replies, xml ) Need Help??


in reply to Re^2: A short meditation about hash search performance
in thread A short meditation about hash search performance

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)).
  • Re-read my post and you'll see that I explicitly acknowledge the fact that hackers do not exactly use big-O notation in the way that Knuth did. Why do you think that he said otherwise?
  • Re-read the root post and you'll discover that pg both misunderstood big-O 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 big-O notation means.
  • Re-read 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.


Comment on Re^3: A short meditation about hash search performance

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://638467]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (8)
As of 2015-07-08 01:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (93 votes), past polls