3 ms·
This is and always has been an important part of understanding what big-O notation actually means. O(1) means constant time, it does not tell you what the const
by dahart 10y ago
This is and always has been an important part of understanding what big-O notation actually means. O(1) means constant time, it does not tell you what the constant is. The constant can be large.
In this case, if your hash always takes 64 bit values and always produces 64 bit values, it is O(1). If your hash were O(log2(N)), then your hash function with an empty table would do 1 bit worth of work, and would do only one operation. But when the table grew to contain 1,000 elements, it would do 10 bits worth of work.
The O(log2(N)) algorithm with N < 2^64 is always faster (in theory) than the O(1) algorithm that does a constant 64 bits of work.
The O(1) algorithm pays off in spades for N >> 2^64, it will become much faster than the logarithmic one, but for small N, log(N) is smaller than 64.
- bogomipz 10y agoRight, a constant i.e unchanging amount of work. I usually think of hashtables though as being O(1) in referring to the look up(amortized) and not the hash code itself.
- dahart 10y agoYep, and a hash table's get is O(1) amortized even when you include the hash function itself, simply because the hash function doesn't change as the hash table grows. @rand_r is right that the hash function is doing C * log2(MAX_N) operations, but that doesn't actually affect the big-O metric, it only affects the run time. :P
- bogomipz 10y agoIndeed, thanks for the clarification.