[rileymat2]

I am not following, isn't this just a graph that shows that how fast operations happen is largely dependent on the odds that it is in cache at various levels (CPU/Ram/Disk)?

The memory operation itself is O(1), around 100 ns, where at a certain point we are doing full ram fetches each time because the odds of it being in CPU cache are low?

Typically O notation is an upper bound, and it holds well there.

That said, due to cache hits, the lower bound is much lower than that.

You see similar performance degradation if you iterate in a double sided array the in the wrong index first.

[adrianN]

O notation is technically meaningless for systems with bounded resources. That said, yes the performance is depending on the probability of cache hits, notably also the TLB. For large amounts of memory used and random access patterns, assuming logarithmic costs for memory access tends to model reality better.