TechFlow news, October 5 — Vitalik published a new article titled "Memory access is O(N^(1/3))", exploring the complexity of memory access in data structures and algorithms. He proposed that under certain architectures or models, the cost of memory access might have an upper bound of O(N^(1/3)). He noted that classical sorting algorithms have a time complexity of O(N log N), but when considering memory access bottlenecks, efficiency analysis for large-scale datasets needs reevaluation.
This topic has significant implications for blockchain system design, especially when handling large-scale state, node synchronization, and data availability (DA / data availability sampling) mechanisms, where efficiency bottlenecks in "reading and writing memory" require careful consideration.
