There's an interesting argument based on physics on why memory access is O(sqrt(N)): http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i http://w

There's an interesting argument based on physics on why memory access is O(sqrt(N)): http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-p... Relevant quote: > The amount of information that can fit within a sphere with radius r can be calculated using the Bekenstein bound, which says that the amount of information that can be contained by a sphere is directly proportional to the radius and mass: N ∝ r·m. So how massive can a sphere get? Well, what is the most dense thing in existence? A black hole! It turns out that the mass of a black hole is directly proportional to its radius: m ∝ r. This means that the amount of information that can fit inside a sphere of radius r is N ∝ r². And so we come to the conclusion that the amount of information contained in a sphere is bounded by the area of that sphere - not the volume! > In short: if you try to squeeze too much L1 cache onto your CPU it will eventually collapse into a black hole, and that would make it awkward to get the results of the computation back to the user. But honestly I find all of these arguments equally pedantic. People often forget Big Oh is a tool just like any other tool. It's useful for estimating number of X, whether X is cpu instructions, cache miss, disk read or whatever. When it stops being a good estimate (whether it's because your real world N is too small for growth rate to dominate, or stuff you're counting are not unit-cost comparable, or you're not even counting the right things in the first place), just stop using it and count cycles on a benchmark instead.