Cairn
guides · cross-cutting lens, not tied to one category

↩ back to Guides

Same Big-O, Different Speed

The distinction: Big-O counts steps, not seconds

Every "choosing a X" guide on this site ranks algorithms mostly by Big-O — how the number of comparisons, probes, or node visits grows with input size. That's the right first filter, and usually the deciding one: an O(n) algorithm beats an O(n²) one at large enough n, no exceptions. But Big-O is explicitly silent about one thing — where the data a step touches actually lives in memory. Two structures can do the provably identical number of steps, at every input size, and still run at measurably different real speeds, because one of them keeps its data packed together and the other scatters it. This page measures the clearest case of that already on this site: Binary Search over a sorted array against AVL Tree lookup. Both are O(log n). Neither asymptotic argument is wrong. The gap between them at scale is real anyway.

Binary Search vs. AVL Tree: identical step counts, measured

Binary Search's own reference implementation halves a sorted array's search window every step: at most ⌊log₂ n⌋ + 1 comparisons, full stop, regardless of what's being searched for. AVL Tree's own contains walks one .left/.right hop per comparison down a tree whose height is proven, on that page's own Complexity section, to never exceed roughly 1.44 log₂ n — a slightly looser bound than the array's, but the same logarithmic shape. Running both reference implementations unmodified, counting every comparison, confirms the two bounds are close in practice, not just on paper: averaged over 200,000 random lookups (half hits, half misses) against the same set of keys, AVL Tree's lookup touches only about 1.9% more elements than Binary Search's at a million keys, and the gap is similarly small at every other size tested.

Timing the identical runs tells a different story. Measured in Node v20.20.2, build-then-query, repeated several times to confirm the pattern holds and not just one lucky run:

navg. steps, arrayavg. steps, treequery time, arrayquery time, treetree ÷ array
10,00012.8613.08~38ms / 200k lookups~31ms / 200k lookups0.8×–0.9×
100,00016.1916.45~44ms / 200k lookups~54ms / 200k lookups~1.2×
1,000,00019.4519.82~70ms / 200k lookups~190ms / 200k lookups2.5×–2.9×

At ten thousand keys, the tree is actually a little faster — small enough that the whole structure, array or tree, fits comfortably in cache regardless of layout, and the array version's slightly more arithmetic per step (computing mid, two comparisons against it) costs more than the tree's one pointer-compare per hop. Past roughly a hundred thousand keys the pattern flips and keeps widening: by a million keys the tree costs 2.5 to 2.9 times longer per batch of lookups than the array, for a provably near-identical number of steps. The step counts barely move between the two structures. The clock does.

Try it: race both, live, in your own browser

This builds a real sorted array and a real AVL Tree — the exact reference implementations from their own pages, unmodified — from the same n random keys, then fires the same 200,000 random lookups (half hits, half misses) at both and reports the real step count and real wall-clock time for each. Building the tree gets noticeably slower than building the array as n grows, and the largest option may take a couple of seconds to build before the race itself starts — but that gap isn't the fair comparison it looks like. The keys this page generates already arrive in ascending order, so "building" the array here is just copying them, an O(n) operation with zero comparisons — not the O(n log n) sort a sorted array would actually need if the input weren't already sorted. See Build cost, measured below for what the gap looks like once the array has to earn its order the same way the tree does.

Average steps per lookup

Wall-clock time for all 200,000 lookups

Press "Run race" to build both structures from the same keys and lookup set, live.

Your own browser's numbers will differ from the Node figures above — different engine, different JIT state, a different machine entirely — but the shape should hold: step counts close together at every n, wall-clock time close (or tree ahead) at 10,000, and a widening tree-is-slower gap by 1,000,000. If it doesn't, that's a genuinely interesting result in its own right and worth not taking this page's word for it instead.

Build cost, measured

The live race above compares a real tree build against an unfairly cheap array "build" — copying keys that were already in order. Timed separately in Node v20.20.2, with the same insertNode/rotation code above building the tree from n keys in random insert order, against Array.prototype.sort actually sorting the same n keys from a genuinely shuffled start (the realistic case: a sorted array built from data that didn't arrive pre-ordered):

narray: copy pre-sorted keysarray: sort shuffled keysAVL Tree: n insertstree ÷ sort
10,000~0.03ms~2.7ms~4.5ms~1.6×–2×
100,000~0.6ms~34ms~75ms~2×–2.2×
1,000,000~7.5ms~415ms~1,580ms~3.7×–3.9×

Against the fair comparison — sort vs. insert, both actually earning the order from scratch — the tree build is still slower, and the gap still widens with n: about 1.6×–2× at ten thousand keys, growing to roughly 3.7×–3.9× at a million. Both operations are O(n log n); the gap is the same constant-factor story as the lookup comparison above, this time from allocating one small object per key plus rotation bookkeeping on every insert, against a flat engine-native sort over one array V8 already owns. Against the unfair comparison — the live demo's own plain copy of pre-sorted keys, which does zero comparisons at all — the gap balloons to two or three orders of magnitude, which is real but measures "copying is cheaper than sorting," not "trees are slower than arrays." Treat the sort-vs-insert numbers above as the honest version of the claim this page's own live demo doesn't actually test.

Why: one contiguous block vs. nodes scattered across the heap

The sorted array backing Binary Search is one contiguous block of memory, allocated once. Every "halve the window" step jumps to a different index, but all of those indices live inside the same block — a block small enough, even at a million entries, that a modern CPU's cache keeps pulling nearby cache lines in ahead of time, and repeated queries during the same race keep reusing memory the first few queries already pulled into cache. The CPU's own prefetcher has a real, physical block to work with.

AVL Tree's nodes are { value, left, right, height } objects, each allocated separately, in whatever order insert happened to create them — which, since the race inserts keys in random order to avoid an already-sorted degenerate build, is not the order a lookup later walks them in. Walking .left/.right from the root means following a pointer to whatever address that node happens to live at, with no guarantee it's anywhere near the node just visited. Past the point where the whole structure no longer fits in cache, each hop has real odds of landing on a cache line the CPU hasn't already fetched — a cache miss, costing a real stall measured in tens to hundreds of CPU cycles, on top of the comparison itself. Binary Search pays that stall rarely, because its memory is one block the hardware can predict. AVL Tree pays it close to once per hop, because its memory is nowhere the hardware can see coming. Same number of hops; a different real cost per hop.

Pitfalls

This isn't "arrays always beat trees." The comparison above is read-only lookup only. AVL Tree exists because it keeps O(log n) insert and delete without shifting anything — the exact operations a sorted array can't do in better than O(n), since inserting into the middle means moving every element after it. A workload with real inserts and deletes mixed in, not just lookups, can easily favor the tree outright; this page measured the one operation (lookup) where both structures are at their theoretical best, on purpose, to isolate the memory-layout effect cleanly.

The crossover point is not a universal constant. Ten thousand and a hundred thousand are where the Node v20.20.2 numbers above happen to cross on this specific machine, for these specific object shapes. A different engine, a different CPU's cache size, or even a newer V8 release optimizing small-object allocation differently could move that crossover meaningfully. Treat the crossover existing at all, and the gap widening with n past it, as the durable claim — not the exact sizes where it happens, which is exactly why the live demo above measures your own browser instead of only repeating the Node numbers.

JavaScript's own number representation adds a wrinkle this page doesn't fully resolve. A plain JS array of small integers is commonly backed by one contiguous buffer of unboxed doubles in V8 in practice — but that's a documented engine optimization, not a language guarantee, and nothing on this page inspects V8 internals to confirm it held during these specific runs. The measured wall-clock numbers are what to trust here, the same way every other timing claim on this site defers to the actual measurement over a guess at the mechanism.

Where this shows up on this site