Why is appending to a growth-doubling dynamic array O(1) amortized when one append copies everything?

## What a dynamic array actually does on append A dynamic array is a growable buffer laid over a fixed-size block of contiguous storage. It tracks two numbers: `count`, how many elements it currently holds, and `capacity`, how many it could hold before the block is full. An append normally writes at index `count` and increments it — a couple of instructions, genuinely constant work. When `count == capacity` there is no room, so the buffer allocates a larger block, copies every existing element into it, releases the old block, and only then stores the new element. That copy touches every element, so *that* append costs `Theta(n)` in the current element count. The claim under examination is: for any sequence of n appends starting from an empty buffer, the **total** work is `O(n)`, so the average per append over that sequence is constant. That is what "amortized `O(1)`" asserts — a bound on a whole worst-case sequence, divided by its length. ## The geometric-series argument Assume capacity doubles at each resize: 1, 2, 4, 8, 16, ... and a resize copies the elements present at that instant. Over n appends the resizes fire when the count reaches 1, 2, 4, ..., up to the largest power of two not exceeding n, and each copies exactly that many elements. Total copies = `1 + 2 + 4 + ... + 2^k`, where `2^k <= n`. A geometric series with ratio 2 sums to just under twice its largest term: `1 + 2 + ... + 2^k = 2^(k+1) - 1 < 2n`. So across the entire run the buffer performs **fewer than 2n element copies in total**, on top of the n constant-time stores. Total `O(n)`; divide by n appends and the amortized cost per append is `O(1)`. The structural reason is worth saying out loud, because it is what the interviewer wants: *each resize buys twice as much headroom as the previous one, so resizes become exponentially rarer at precisely the rate at which they become more expensive.* Cost per resize grows like `2^k`; frequency of resizes falls like `1/2^k`. The product is constant, and constant per-append cost is exactly what "amortized `O(1)`" means. ## The same result seen per element Count from the elements' side instead. An element added after the most recent doubling has never been copied — and roughly half the elements sit in that band. Of the rest, half of those were copied once, half of the remainder twice, and so on. An element inserted at position `i` is copied only by doublings that happen after it arrives, which is at most about `log2(n/i)` times. Summing that over all positions gives `O(n)` again. So the intuition "everything is copied on every resize, therefore the work must be superlinear" is wrong twice over: most elements are copied a handful of times, and the newest half are never copied at all. The very first element is the unlucky one, copied about `log2(n)` times over the run — which is still cheap. ## What the bound does not promise Amortized is a statement about a **total over a sequence**, not a promise about any single call. Somewhere inside those n appends there is one that copied every element and took `Theta(n)`. If the caller has a per-operation deadline rather than a throughput target, the amortized bound is the wrong guarantee to quote. It is also not the same idea as an average over randomly distributed inputs: no input distribution is assumed anywhere in the argument above, and the bound holds against an adversary who picks the operation order. ## The memory side of the bargain Doubling means capacity never exceeds twice the count immediately after a growth, so at most half the allocated slots are idle at any moment. The wasted fraction is *bounded*, not growing — a fixed tax in exchange for linear total copying. This matters because the most common objection to doubling ("it wastes memory") imagines unbounded waste, when the overhead is capped by construction. ## Two ways the argument breaks First, if capacity grows by a **fixed additive step** instead of a multiplicative factor, resizes stop becoming rarer — they fire at a constant rate forever while each one costs more — and the copy work becomes quadratic. Multiplicativity is the load-bearing part of the proof, not doubling specifically. Second, if the buffer also **shrinks** on removal at the same threshold it grows at, an alternating append/remove sequence sitting exactly on the boundary forces a full copy on every single operation, destroying the amortized bound. Practical designs shrink at a lower occupancy (for example, halving only when the buffer falls to a quarter full) so that a burst of cheap operations must occur between any two expensive ones.