[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.