Vitalik published a new article questioning the assumption that "memory access is O(1)."

ChainCatcher news, October 5, Ethereum co-founder Vitalik Buterin published a new article titled "Memory access is O(N^(1/3))" exploring the complexity of memory access, discussing the complexity issues of "memory access" in data structures and algorithms.

The article states that arithmetic operations (addition, multiplication, division, etc.) for fixed-size numbers are typically considered to require one time unit, and memory access is also considered to require one time unit, but this assertion is inaccurate. In both theory and practice, memory access requires O(N^(1/3)) time: if your memory is 8 times larger, the time required for read and write operations will increase by 2 times.
Vitalik points out that this rule has practical implications in cryptography and algorithm optimization, and calls for future computational models to more accurately reflect memory hierarchy and physical limitations.