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'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:
| n | avg. steps, array | avg. steps, tree | query time, array | query time, tree | tree ÷ array |
|---|---|---|---|---|---|
| 10,000 | 12.86 | 13.08 | ~38ms / 200k lookups | ~31ms / 200k lookups | 0.8×–0.9× |
| 100,000 | 16.19 | 16.45 | ~44ms / 200k lookups | ~54ms / 200k lookups | ~1.2× |
| 1,000,000 | 19.45 | 19.82 | ~70ms / 200k lookups | ~190ms / 200k lookups | 2.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.
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
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.
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):
| n | array: copy pre-sorted keys | array: sort shuffled keys | AVL Tree: n inserts | tree ÷ 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.
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.
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.
insert,
deleteMin, and deleteMax in O(log n) — but Min-Max Heap's own
Complexity section measures 1.5×–1.9×
more comparisons and 2×–9× more wall-clock time per delete, from scanning six grandchild/child
candidates and allocating two fresh arrays to do it, not from any gap in the shared bound.decrease-key
density (about 1.5× at 2 relaxations/vertex) and only falls behind once that density climbs into
the hundreds — a crossover driven by which structure's bookkeeping actually pays for itself at a given
workload, not by the two structures' shared Big-O.O(|A|·|B|) order, but Jaro-Winkler's matching pass breaks out of its window
scan the moment it finds a match, while the DP table has to fill every cell regardless —
measured at 8×–20× fewer comparisons,
averaging 13×, across fifteen real name-length pairs.