I think there is a key point in the FAQ (article four, all linked through the series): > You are conflating Big-O with memory hierarchies > No, I’m applying B

I think there is a key point in the FAQ (article four, all linked through the series): > You are conflating Big-O with memory hierarchies > No, I’m applying Big-O to memory hierarchies. Big-O is a tool, and I am applying it to analyze the latency of memory accesses based on the amount of memory you are using. As some others have pointed out, the line is crossing hierarchies of cache, and that he is not looking at the big O of instructions. Both of these are accurate, and the author is aware of this. He is using the tool of big O analysis to measure a performance characteristic. That characteristic is not the traditional number of instructions or amount of memory utilized in the computation of an algorithm. It is the latency for access to a random piece of data stored on a system. There are two cases considered, the practical, and the theoretical. At the practical level, we do not have a unified physical implementation of the address space in a modern computer. This means that accessing a random address in memory is an action that will most likely cross levels of the cache hierarchy. It is well known that there are order of magnitude jumps crossing these levels. Perhaps it is uninteresting to you, and the importance of cache locality in an algorithm is something that you already have a very strong handle on. That makes his observation of time-to-access a random address trivial, but not wrong. Big O tells us that a binary search is the most efficient search algorithm for an array (constraint - the array must be sorted), but in practice a linear search with a sentinel value across an unsorted array will be faster if the array fits in cache. Keeping in mind the big O latency of random memory access across cache hierarchy levels would be the theoretical analysis to tell us this. The traditional big O looks at number of instructions. These are both valid tools in choosing an optimal algorithm. The second point the author makes is the theoretical limit. Assume the ideal storage medium with minimum access latency and maximum information density. This storage medium is matter. The limit of packing is the point at which you would create a black hole. With this ideal storage medium, you cannot pack an infinite amount of data within a distance that can be traversed at the speed of light within one clock cycle. For this colossal storage array, there are some addresses which cannot be physically reached by a signal moving at the speed of light within the amount of time that a single clock cycle (or single instruction) takes. Accessing a random address is not a constant time operation, though the instruction can be dispatched in a constant time. There is a variable time for the result of that instruction to return to the processor. At this theoretical limit, we would still end up with a cache hierarchy, though it would be 100% logical. With a single storage medium and unified address space, the cache hierarchy would be determined by physical distance from CPU to physical memory location. Those storage cells (whatever form they take) that can be round-tripped by a speed of light signal in one clock cycle are the first level of cache, and so on. You could have very granular, number-of-clock-cycles cache levels stepping by one at each concentric layer of the sphere, or you could bucket the number of clock cycles. Either would effectively act as a cache. This theoretical exercise is an extreme limit, but bears out the practical implications that our current physical implementations of cache hierarchy exhibits in practice. Again, perhaps these observations are trivial, but I believe they do stand up to scrutiny. The key insight is that the performance characteristic being described by big O is time, not the more traditional space or number of instructions. I think time is a valuable metric in terms of algorithm selection. If we think about end users - they don't care that one instruction or 1,000,000,000 are being executed. They care about how quickly work is done for them by the computer. Instruction-based analysis can be a huge help in this consideration, but so can time-based analysis. Neither should be ignored, and neither invalidates the other.