Memory access is O(N^[1/3])

Summary

Memory access is O(N^[1/3]) 2025 Oct 05 See all posts Memory access is O(N^[1/3]) In computer science, we often compare the efficiency of algorithms by describing their runtime as a function of the size of the input. Sorting is O(n * log(n)), meaning that sorting a list of N items takes an amount of time proportional to the number of items multiplied by its logarithm. Matrix multiplication is somewhere between 2.37 and 2.8, depending on the choice of algorithm. But these estimates are all relative to some model of how long it takes for the underlying machine to perform some basic underlying operations. Typically, arithmetic operations (addition, multiplication, division...) are considered to take one unit of time for fixed-size numbers, and memory accesses are also considered to take one unit of time. In this post, I will argue that this choice for memory access is wrong. Memory access, both in theory and in practice, takes O(N^⅓) time: if your memory is 8x bigger, it will take 2x longer to do a read or write to it. I will also show an example of an application where this concretely matters. The theoretical argument Imagine you have a processor sitting in the middle of a pile of memory. The processor's ability to talk to any individual piece of memory is bounded by the speed of light, ergo the delay is proportional to distance. In a three-dimensional world, you can fit 8x as much memory within 2x the distance from you. Double the distance, eight times the memory. This covers sequential access. In practice, of course, a CPU is not literally situated inside of a homogeneous cube of memory, and electrical signals don't travel exactly in a straight line (and, for that matter, are slower than light). But, as we will see later, the model is surprisingly close to accurate in practice. For parallel access, things get more subtle and depend on the medium. If you think of read and write as occupying a "wire" of the needed length for a fixed length of time, then you get the sa...