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

vitalik.eth.limo · 1,000 words · saved by 3 readers

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 wher

Dark Mode Toggle 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 b

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

saved by

related reading