Binary search is O(log n). Linear scan is O(n). So binary search is faster, right? On a 64-element array of integers, it usually isn’t. The linear scan wins — often by 2–3× — and it keeps winning up to a few hundred elements. If your mental model of performance stops at the asymptote, that result looks impossible. The machine disagrees.

What Big-O Actually Promises

Big-O describes how cost grows as n grows. It says nothing about the cost of a single step, and it deliberately throws away constants. 100000n and 0.1n are both O(n). That’s fine for what the notation is for — comparing growth rates — but “which of these two functions is smaller at n = 200” is a different question the notation was never designed to answer.

On modern hardware, the constant factors aren’t small perturbations. They span four orders of magnitude:

text
   L1 cache hit          ~1 ns
   L2 cache hit          ~4 ns
   Main memory           ~100 ns
   Branch mispredict     ~15-20 cycles thrown away

An algorithm that does 5× more work but stays in L1 beats one that does less work but misses to DRAM on every step. That’s a 100× per-step penalty against a 5× step-count advantage.

A linear scan over an int array touches memory sequentially. The hardware prefetcher notices the pattern after two cache lines and starts pulling data in before you ask for it. Each comparison is a predictable branch (almost always “keep going”), so the pipeline stays full. Sixteen ints fit in one 64-byte cache line — the scan reads a line, does 16 comparisons, reads the next.

Binary search does the opposite of everything the hardware likes. Every probe jumps to an unpredictable address, so the prefetcher is useless. Every comparison is a 50/50 branch, so the predictor is wrong half the time. On a small array none of this matters much — everything’s in L1 either way — but the scan’s simplicity still wins. On a large array, binary search wins on step count but every one of its ~30 probes is likely a cache or TLB miss.

The same story plays out elsewhere:

  • Hash map vs. sorted vector. For small n, std::vector + linear scan beats std::unordered_map on lookups — no hashing, no pointer chase, no allocation. This is why so many codebases carry a SmallMap type.
  • Insertion sort inside quicksort. Every serious sort implementation switches to insertion sort below ~16 elements. O(n²) with sequential access and no recursion overhead beats O(n log n) machinery at that size.
  • Linked lists vs. arrays. O(1) insertion is a lie of omission if finding the insertion point costs a pointer chase per node, each one a potential cache miss.

Measuring the Crossover

The only honest answer to “which is faster” is a measurement on your data sizes. A minimal harness:

c
#include <time.h>

static double bench(int (*f)(const int *, int, int),
                    const int *a, int n, int key, int iters) {
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    volatile int sink = 0;
    for (int i = 0; i < iters; i++)
        sink += f(a, n, key + (i & 7));   /* vary the key: defeat the predictor */
    clock_gettime(CLOCK_MONOTONIC, &t1);
    return (t1.tv_sec - t0.tv_sec) * 1e9 + (t1.tv_nsec - t0.tv_nsec);
}

Two details matter more than they look: the volatile sink stops the compiler from deleting your benchmark, and varying the key stops the branch predictor from memorizing one search path and giving you a fantasy number. Run it across sizes and you get a crossover table, not an opinion.

When the Asymptote Does Win

None of this makes Big-O wrong. Past the crossover point, growth rate is destiny. An O(n²) algorithm at n = 10⁶ is dead no matter how cache-friendly it is — 10¹² operations doesn’t care about your prefetcher. The failure mode I actually see in the wild is almost never “used the asymptotically worse algorithm at scale.” It’s the opposite: paying pointer-chasing, allocation, and hashing overhead at n = 20, in a loop, millions of times, because the “right” data structure was chosen by notation instead of by measurement.

Takeaways

  • Big-O compares growth rates. It cannot compare two algorithms at a fixed n.
  • Memory access pattern is usually the dominant constant: sequential + predictable beats clever + random until n gets large.
  • Real libraries encode this: introsort’s insertion-sort cutoff, small-size optimizations, B-trees instead of binary trees.
  • Find crossover points by measurement, with varied inputs and a volatile sink.
  • At large n, the asymptote always wins. Know which regime your n lives in.