Amortized Analysis & Dynamic Arrays

The expanding shelf row

Back at your sorting desk, you're managing a row of storage shelves for incoming packages. Normally, you have a designated row of shelves for incoming packages, and when a new package arrives, placing it in the next empty shelf slot is incredibly easy — just slide it in. But what happens when the row of shelves is completely full? You have to move your entire setup to a new, larger location. This is a massive, exhausting move: you must pick up every single package on the shelf and carry them, one by one, to the new rack.

To make sure you don't spend all your time moving, you establish a rule: whenever your current shelf fills up, you build a new one that is exactly twice the size of the old one. The moves get larger and further apart, but they also become rarer, since it takes longer and longer periods of quick, single-slide-ins between moves.

This is a different question than the case-analysis lessons asked. The case-analysis lessons asked "what's a typical input?" — best, worst, average, all about a single call on inputs that differ. Amortized analysis asks something else entirely: in any sequence of m operations on the same structure — including an adversarial one — what's the total cost, divided by m? No probability anywhere; it's a worst-case statement, just about a sequence instead of a single call.

Charging peaks to quiet neighbors

The canonical example: appending to a dynamic array (Python list, JS array). Normally an append just writes to the next free slot: O(1). But when the array is full, it has to allocate a new block twice the size and copy every existing element into it before the new item can go in: O(n) for that one append. Watch what that actually costs across a run, starting from capacity 1:

Most appends cost 1. The expensive ones (resizes) get rarer exactly as fast as they get bigger — they happen once the array reaches size 1, 2, 4, 8, … doubling each time, exactly like your shelf-doubling rule. Summing every cost through append 9 gives 24, for an average under 3 per append — even counting every spike. In general, for n appends the resize costs are 1 + 2 + 4 + ⋯ + n/2 ≈ n, plus n ordinary O(1) writes: about 2n total work for n appends → O(1) amortized per append. Watch the schedule play out — the work counter is the whole argument:

That direct sum works because we could see the whole resize schedule laid out in advance. Here's a technique that proves the same bound without needing to precompute anything — the accounting method, and it's the standard tool for amortized proofs you'll meet again later in the course. Imagine that every time you place a new package, you charge yourself 3 tokens, not 1: one token pays for the placement happening right now, and two tokens go into a bank tied to that package. Consider the moment the shelf fills up and the next package triggers a move, which must carry every one of its n current packages. The shelf was last expanded when it held n/2 packages (that move doubled its capacity to n), so exactly the newest n/2 of the current packages were placed since that last move — and each of those is still carrying its 2 banked tokens, for exactly n tokens sitting in the bank. That's exactly enough to pay for carrying all n packages at 1 token each: the older surviving n/2 packages already spent their own banked tokens paying for the previous move, so it's the newer half's bank, not their own, that covers this one. No move ever needs to draw on an empty bank, so a flat charge of 3 tokens genuinely covers everything, spikes included. That's the proof — and it exposes why the growth factor has to be multiplicative.

The failure of fixed growth. Now, imagine if you tried to save shelf space by only adding 10 shelves at a time instead of doubling. This means a grueling move of all the packages to a brand-new rack has to happen every single time you exceed your current 10 new packages. The effort of those moves becomes constant, and your banking system completely broke. Grow by a fixed +10 slots instead of doubling, and a resize (cost ~n) comes due every 10 appends regardless of how large the array already is: total work ~n²/20 for n appends, i.e. O(n) amortized — quadratic, not constant. Doubling isn't a stylistic convention; it's the one thing that makes the banking argument close.

Using the right lens

The skill isn't memorizing this table — it's asking, whenever you hear a bare complexity claim, "over what: the worst input, a random input, or a long sequence of operations?" Those are three different promises, and conflating them is where most "but I thought this was fast" surprises come from.