Vitalik Releases New Article “Memory Access is O (N^ [1/3])”: Exploring Memory Access Complexity and Blockchain System Efficiency
TechFlame
2025-10-05 03:24
TechFlame2025-10-05 03:24
English
On October 5, Vitalik published a new article “Memory Access is O (N^ (1/3))” which explores the complexity of memory access, discusses the complexity of “memory access” in data structures and algorithms, and suggests 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 the time complexity of classical sorting algorithms is O (N log N), and when considering memory access bottlenecks, efficiency analysis of large-scale data sets needs to be re-examined.
This topic is instructive for blockchain underlying system design. In particular, when dealing with large-scale state, node synchronization, and data availability (DA/data availability sampling, etc.) mechanisms, the efficiency bottlenecks of “read/write memory” need to be carefully considered.