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

↩ back to Guides

In-Place vs. Out-of-Place

The idea: mutate, or allocate a copy?

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 vs. Merge Sort: the clearest instance already on this site

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 vs. Binary Heap: the same pattern, a different shape

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.

Try it: the tax, isolated

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.

Pick a size and click Measure — it runs both versions (best of 5 repeats each, to cancel out JIT warmup noise) on an identical array built fresh for each repeat, and times both with the same clock.

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.

Where else this shows up

Pitfalls

"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.