Vitalik publishes new article "Memory access is O(N^[1/3])": Exploring memory access complexity and blockchain system efficiency

On October 5, Vitalik published a new article titled "Memory access is O(N^(1/3))" to explore the complexity of memory access. He discussed the issue of "memory access" complexity in data structures and algorithms, proposing that under certain architectures or models, the cost of accessing memory may have an upper bound of O(N^(1/3)). He pointed out that while the classic time complexity of sorting algorithms is O(N log N), when considering the memory access bottleneck, it is necessary to re-examine the efficiency analysis for large-scale datasets. This topic is particularly enlightening for the design of blockchain underlying systems, especially when dealing with large-scale state, node synchronization, and data availability (DA/data availability sampling, etc.) mechanisms, where the efficiency bottleneck of "reading and writing memory" must be considered with greater caution.