Re:A new fast hash table in response to Google’s new fast ha...
by 0xffff2 on Tuesday May 29, 2018 @01:43PM
(#17181344)
We're really talking about a system with finite memory, and taking O(1) to be equal to log(n) when n is such that the data entirely fills the memory. Under these conditions, O(log(n)) gives a tighter and more accurate bound, but at the expense of not being strictly correct (i.e., it is not truly an asymptotic bound.)
Re:A new fast hash table in response to Google’s new fast ha...
by bzbarsky on Tuesday May 29, 2018 @03:12PM
(#17182117)
It all depends on what you want your constant to be.
If your constant is "the worst-case time it takes to swap in the memory from my disk", and your dataset is guaranteed to fit in local disk then memory access is in fact O(1). With a really bad constant. But in practice people care about how much better than that you can do...
Now technically the "guaranteed to fit in local disk" assumption means you're really no considering asymptotic behavior. But then the question is what one really means by asymptotic behavior in this case. What do you consider your "memory access" latency to be once your dataset is too big for the sum total of all existing storage media?
Quite the opposite — O(1) is in fact too tight.