Why two O(n²) loops can run 15× apart

Two nested loops can do the same work, have the same O(n²) complexity, and still run around 15× apart. A visual explainer on why: the RAM model, the memory wall, cache lines, locality, L1/L2/L3, prefetching, data layout and false sharing. It also covers how the timing difference between a cache hit and miss became the side channel behind Spectre and Meltdown. submitted by /u/Ok_Marionberry8922 [link] [留言]