Comment by bzbarsky

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?