Amortized analysis

Big idea

Amortized cost is the average cost per operation over a long sequence, even when a few individual operations are expensive. If the rare expensive step pays for itself across many cheap ones, the operation is "amortized O(1)".

The puzzle: appending to a dynamic array

Python lists, Java ArrayList, and C++ vector all sit on a fixed-size block of memory. When it's full, the next append must:

1. allocate a bigger block,
2. copy every existing item into it,
3. then add the new item.

That copy is O(n). So is append O(n)? Not on average — because of how much bigger the new block is.

Doubling makes it cheap

Grow by doubling the capacity each time. Start at capacity 1 and append 16 items:

Total copies for 16 appends: 1 + 2 + 4 + 8 = 15. In general, n appends cause fewer than 2n copies in total, because 1 + 2 + 4 + … + n/2 < n. Spread over n appends, that's under 2 copies each — O(1) amortized.

Loading diagram

Watch it

Why growing by a fixed amount fails

Grow by +10 slots each time instead. Every 10 appends trigger a copy of the whole array: 10 + 20 + 30 + … + n ≈ n²/20 copies. That's O(n) amortized per append — n appends cost O(n²). The ratio (×2, or ×1.5 in some libraries) is what makes it work.

Amortized is not average-case

They sound alike but mean different things:

• Average case is about random inputs: on a typical input, how long does it take?
• Amortized is a guarantee over a sequence: on any sequence of n operations, the total is at most this — no luck involved.

A single append can still take O(n). If you need every operation to be fast (say, a real-time audio loop), amortized O(1) may not be good enough.

Where else you'll see it

• Hash tables resize (and rehash everything) when they get too full — amortized O(1) inserts. See hashing.
• A queue built from two stacks: each item is moved between stacks at most once, so each operation is amortized O(1). See queue.
• Monotonic stacks: each item is pushed once and popped at most once, so a loop with an inner while pop is still O(n) overall. See monotonic stack.
• Union-find with path compression: nearly O(1) amortized per operation. See union-find.

The monotonic-stack argument is worth remembering on its own: if every item enters and leaves a structure at most once, the total work is O(n) no matter how the loops look.

Quick check