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.