It's a very interesting experiment/conclusion, but it rests upon one assumption: The assumption that the entire dataset has been preloaded into the L1/L2/L3 cac

It's a very interesting experiment/conclusion, but it rests upon one assumption: The assumption that the entire dataset has been preloaded into the L1/L2/L3 caches. This assumption is a shaky one to make, and is easily violated. Imagine if you have a hashmap that is small enough to fit entirely in L3 cache. However, most of it has been evicted from the L1/L2 caches, by other data that the core has been reading/writing to as well. Eventually, the thread returns to the hashmap and performs a single lookup on it. In this scenario, the time required will indeed be O(1). So what you really have is a best-case-complexity of O(sqrt(N)), if your data has been preloaded in the closest possible caches, and a worst-case-complexity of O(1) if your data is stuck in an outer level cache/DRAM. Given that we usually care more about the worst-case-scenarios, not the best-case-scenario, using the O(1) time complexity seems like a reasonable choice. Going back to the author's premise that the time-complexity of a single memory access is O(sqrt(N)), not O(1), this is true only where N represents all/most of the dataset being processed. If N represents only a small fraction of the dataset being processed, and your caches are going to be mostly filled with other unrelated data, then the time complexity is closer to O(1). Clearly the O(sqrt(N)) is more accurate than O(1) under some circumstances, but even so, it's not clear what benefit this accuracy confers. All models are inaccurate simplifications of reality, but simple-inaccurate models can still be useful if they can help in decision-making. Big-O analysis isn't used to estimate the practical running-time of an application. For that, you'd be better off just running the thing. Big-O analysis is more used to compare and decide between different competing algorithms/data-structures. And in that sense, whether you choose to model linked-lists/binary-search/hash-maps as O(Nsqrt(N))/O(log(N)sqrt(N))/O(sqrt(N)), or O(N)/O(logN)/O(1), the recommendation you end up with is the same.