Comment by lelandbatey

The author of that post effectively re-defines "memory"/"RAM" as "data", and uses that to say "accessing data in the limit scales to N x sqrt(N) as N increases". Which, like, yeah? Duh, I can't fit 200PB of data into the physical RAM of my computer and the more data I have to access the slower it'll be to access any part of it without working harder at other abstraction layers to bring the time taken down. That's true. It's also unrelated to what people are talking about when they say "memory access is O(1)". When people say "memory access is O(1)" they are talking about cases where their data fits in memory (RAM).

Their experimental results would in fact be a flat line IF they could disable all the CPU caches, even though performance would be slow.