# Big-O in Practice: When the Constant Factor Eats the Asymptote

> Binary search loses to linear scan on small arrays. Hash maps lose to sorted vectors. Big-O tells you how algorithms scale, not which one is faster — and on modern hardware the gap between those two questions is enormous.

URL: https://harshith.in/blog/big-o-in-practice/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: algorithms, performance, fundamentals

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.

## Why the Scan Beats the Search

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.