Most Complexity sections on this site already state a space bound — O(1) extra,
O(n) extra, O(log n) for a recursion stack. What they usually don't say
is what happens at the exact moment that extra space gets allocated, and what that moment costs
in wall-clock time, not just in the final tally of bytes held. Two algorithms can share an
identical time complexity and still differ sharply here: one mutates the data already sitting in
memory, the other builds a fresh structure to hold its answer. This is a different question from
Space for Time's (which asks about memory spent
before any operation runs, to make every later query cheaper) and from
Same Big-O, Different Speed's (which compares
two different structures' memory layout — contiguous array versus scattered heap nodes —
not whether a single operation allocates as it goes). Here the question is narrower and more
mechanical: inside one call that already has to do O(n) (or O(log n), or
whatever) work regardless, does that work also pay for a fresh array or object along the way — and
how much does paying for it actually cost, measured against an equivalent that doesn't.
Quicksort and Merge
Sort are both O(n log n) average case, and that page's own measured comparison
found merge sort actually wins on raw comparison count — about 26%-32% fewer, widening with
n, from always getting a perfect halfway split that quicksort's last-element pivot
never guarantees. Comparison count says merge sort should win. Wall-clock says the opposite,
by a wide and growing margin: measured directly against both
pages' own shipped quickSort/partition and mergeSort/
merge functions, merge sort runs roughly 2.3× slower at
n = 10,000, widening to roughly 2.7× slower at n =
1,000,000. The reason named on that page is exactly this lens: merge's own
arr.slice() calls and out.push() builds allocate a brand new array at
every level of the recursion, while quicksort's partition swaps two elements in the same array and
allocates nothing. Fewer comparisons, more allocations, and merge sort still loses the race —
comparison count was the wrong proxy for the real cost, and the allocation tax is the reason why.
Min-Max Heap and Binary Heap are both O(log n) for
deleteMin/deleteMax, and by raw comparison count Min-Max Heap's own
measured Complexity section already
shows it paying a real but modest premium — roughly 1.5×-1.9× more
comparisons across a mixed workload, from needing to find the smallest (or largest) among six
candidates per step instead of Binary Heap's two. Wall-clock opens that gap much wider —
2×-3× at a few thousand elements, growing to
8×-9× by a few hundred thousand — and the page's own explanation is,
again, allocation: every deleteMin/deleteMax step builds two fresh
arrays (the candidate's children and grandchildren) and scans one with includes(),
overhead a flat two-comparison siftDown never pays at all. Same mechanism as
Quicksort/Merge Sort, a smaller comparison-count gap to start from, and still the dominant cost
once wall-clock is what's actually measured.
Both examples above bundle the allocation cost together with a real algorithmic difference
(a different pivot and split shape; a six-candidate scan instead of two). To see the allocation
tax on its own, with nothing else different, this runs the same trivial O(n) job —
double every element — two ways on an identical array: a plain for loop mutating the
array in place, and Array.prototype.map, which allocates and returns a brand new
array of the same length. Same work per element, same final answer, same asymptotic class — the
only difference is whether a new array gets built.
Measured directly in this same way ahead of shipping (Node v20.20.2, best of 5 repeats): roughly
1.3×-1.5× slower out-of-place at n = 1,000-10,000,
widening to roughly 2.7×-3.2× by n = 1,000,000 and
beyond — smaller than either named comparison above (there's no extra algorithmic work riding
along here, just the allocation itself), but the same direction and the same growing-with-n
shape. Your browser's own numbers will differ from Node's — different engine, different JIT — but
the trend should hold.
O(log n)-node path on every write, since almost any node could need a new value in
some future version" — out-of-place taken to its logical extreme, paying a real per-write
allocation bill specifically to keep every old version reachable. That page's own structure
mostly escapes the bill (O(1) amortized per union, not O(log n)) only
because of a one-write-per-node invariant most structures don't have — the general case really
does pay what it looks like it should.put in 100,000 doing 98,305×
the work of an ordinary one, from a single bucket-array reallocation. Not a design choice between
two algorithms the way the sections above are — named here because it's the same underlying tax,
just paid all at once on a schedule instead of being a live design trade-off.O(1) extra space, the whole reason it beats Merge Sort's guarantee on memory) —
named here as the comparison-sort family's own clean in-place example, alongside Quicksort above."In place" is a property of one call, not of an algorithm's whole reputation.
Quicksort's partition allocates nothing, but the recursion itself still costs O(log n)
stack space — genuinely smaller than Merge Sort's buffers, but not literally zero. Read the actual
Space line on a page rather than assuming "in-place" means "no extra memory at all anywhere."
Fewer comparisons doesn't mean faster — allocation can dominate a smaller op count. Both sections above measure an algorithm that does strictly less comparison work (Merge Sort; Min-Max Heap, closer to even) losing the real race anyway. Comparison count and allocation count are different ledgers, and this lens exists because the second one is so often left unpriced.
The gap isn't fixed — it grows with n in every case measured on this
page. 2.3× to 2.7×, 2×-3× to 8×-9×, 1.3× to
3.2×: every single comparison above widens at larger sizes, never narrows. An allocation's
cost scales with how much it copies; a mutation's doesn't need to copy anything at all. Don't
assume a gap measured at one size holds at another without rechecking — the direction seems stable
sitewide, the magnitude isn't.