Do you know where your variables are? | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
"And a billion differs from 1 only by a constant - so that's O(1)" You obviously don't understand what O(1) means. Say we have an array of 1 billion elements. Let's look at two different search algorithms:
As everyone knows, the performance of those two approaches are so different, but according to your theory, they are both O(1)! The math here is so off! Well... I certainly don't mind if you insist your idea, but please don't confuse the general public. What you said would be right, if we put a restriction saying that a hash can contain at most 1 billion elements. As O(1 billion) has the same complexity as O(1), even though 1 billion is much bigger than 1. However O(n) is more complex than O(1 billion), even comparing with O(1 billion ** 1 billion), O(n) is still more complex. Why? because n is a variable, which can go to unlimit. 1 billion ** 1billion is huge, but n is going to unlimit, and evetually it will pass 1 billion ** 1 billion. In our context, please remember that, the size of a hash is a variable (that potentially goes to unlimit), and your analysis has to reflect this fact. Don't confuse it with the size of a given hash at a given time. In reply to Re: Re: A short meditation about hash search performance
by pg
|
|