2 ms·
Right, 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 cod
by bogomipz 10y ago
Right, 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.