Comment by OskarS
8 years ago
I mean, yeah, obviously, I'm not disputing that, but the point is that it's still "constant time", it doesn't scale with the amount of memory.
My point wasn't that it doesn't get slower if you have larger datasets: of course there's a change when you go from cache-hits to cache-misses. My point was that trying to say "it has higher complexity than O(1)" is an inaccurate way of describing that slow-down. "O(1) random memory access" doesn't mean "fast memory access", it means "memory access where the time is bounded by a constant".
That's because people use big-oh notation when they really mean something close to theta-oh and are looking for a tighter average case bound (e.g. any graph where you benchmark 'average' case data).
E.g. for almost any commonly used algo you could say it is O(e^n) and you would be technically correct as far as what big-oh demands.
O(1) is indeed an upper bound on memory access, but in the presence of cache it is not the tightest possible bound, hence one reason for divergence against numerical estimates given by rough big-oh bounds.
> O(1) is indeed an upper bound on memory access, but in the presence of cache it is not the tightest possible bound, hence one reason for divergence against numerical estimates given by rough big-oh bounds.
Quite the opposite — O(1) is in fact too tight.
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.)
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?