When Big-O and Your Benchmarks Disagree — Caches, Branches, and Memory Bandwidth

Two O(n) programs can differ by orders of magnitude in the real world. This article unpacks what Big-O deliberately throws away — cache hierarchies, branch prediction, and memory bandwidth — and how to reason about each.

Same O(n), wildly different speed

Maybe this has happened to you. You did the textbook analysis, picked the O(n) algorithm, and the program still crawled. Or you benchmarked two implementations with identical complexity and one was dozens of times faster than the other.

Two concrete puzzles. First: summing n numbers. Walking an array from the front and walking a linked list (where each element stores the address of the next one) both visit every element once — both are O(n). Yet for large n, the array version is typically faster by orders of magnitude. Second: summing every element of a 2D array. Sweeping row by row and sweeping column by column are both O(n²), but on a large array the measured times diverge dramatically.

Big-O is not wrong. Big-O only describes how the number of steps grows as n grows — it deliberately says nothing about how heavy each step is. And on real hardware, the cost of a single step can swing by a factor of hundreds depending on how you touch memory. This article walks through the three main culprits behind that swing: caches, branch prediction, and memory bandwidth.

A metaphor: your desk, the bookshelf, and the warehouse

Picture the CPU as a clerk writing a report from reference books. The books live in three places:

1. On the desk: reachable in an instant, but only a few fit
2. The bookshelf behind you: stand up, a few seconds, holds dozens
3. The warehouse in another building: minutes per retrieval, but it holds everything

That is the memory hierarchy. The desk is the CPU's cache; the warehouse is main memory (DRAM). On real machines the nearest and farthest storage differ in access time by roughly two orders of magnitude.

There is one more crucial detail. When you request a single book, the warehouse worker brings the whole box it was packed in, neighbors included. If the next book you need is already in that box, no trip to the warehouse. That box is a cache line (64 bytes on most CPUs). The consequence: a clerk who reads books in shelf order is fast; a clerk who fetches one book from a different box each time is slow — even if both read the same number of books.

The assumption Big-O quietly makes

Complexity theory is built on an idealized machine called the RAM model, in which reading any memory address costs exactly one step. That assumption is what keeps the theory clean and lets us compare algorithms on their essential merits (we covered this foundation in complexity basics).

The relationship to wall-clock time fits in one line:

Here $T(n)$ is the actual running time, $f(n)$ is the shape Big-O talks about (n, n², and so on), and $c$ is the constant factor — the average cost of one step. Put in words: the time you actually wait is the shape of the growth curve multiplied by how expensive a single step happens to be on your machine. Big-O discards $c$ and compares only $f(n)$. But in measurements, $c$ is often what dominates: if cache behavior moves $c$ by 100×, two O(n) programs end up 100× apart. And at realistic values of n, the gap in $c$ is frequently larger than the gap between the curves themselves.

From here on we open the three drawers hiding inside that constant $c$ — caches, branch prediction, and memory bandwidth — and for each one go all the way down to why it bites, how to measure it, and how to fix it.