Amortized analysis — aggregate, accounting, potential methods: Visual walkthrough

Step 1 — What a dynamic array actually is (the boxes)

WHAT we are looking at: a strip of $s$ boxes, with the leftmost $n$ of them shaded (holding data) and the rest empty (reserved but unused).

WHY these two numbers: because the entire cost drama lives in the gap $s - n$ . When the gap is $> 0$ , a push is trivial — drop your item in the next empty box. When the gap hits $0$ (array is full, $n = s$ ), there is nowhere to put the next item, and something expensive must happen. Everything below is about that moment.

PICTURE:

Figure — Amortized analysis — aggregate, accounting, potential methods

Step 2 — The cheap push vs. the expensive push

WHAT: the picture shows both events side by side. On the left, a green arrow drops one item into a waiting empty box. On the right, the strip is full, so we allocate a longer strip and drag every old item over (the orange copy arrows) before we can place the new one.

WHY we must copy: memory is contiguous — the reserved boxes sit next to each other physically. To get a bigger contiguous block we must ask for fresh memory elsewhere and physically move the data. There is no way to "just extend" the old strip.

PICTURE:

Step 3 — The key design choice: double the capacity

WHAT: the picture is a timeline of pushes. Each tick is one push. The rare tall orange bars are the resizes (at $n = 1, 2, 4, 8, 16$ ); every other tick is a short green bar (a cheap $O (1)$ write).

WHY doubling wins (in one sentence): doubling turns the sizes of the expensive copies into a geometric series ( $1, 2, 4, 8, \dots$ — each term doubles), and the whole magic below is that a geometric series is dominated by its last (biggest) term — it is not the sum of many big terms like the arithmetic sum above.

PICTURE:

Step 4 — Aggregate method: add up ALL the copy costs

WHAT: stack the copy costs $1, 2, 4, 8, \dots$ as nested bars. Each bar is (just barely) taller than all the shorter bars stacked together — so the grand total is a hair under twice the tallest bar.

WHY this kills the " $O (n)$ per push" myth: yes, one copy is huge, but the huge ones are so rare that all copies summed is only $\approx 2 m$ , not $m \cdot n$ .

$T (m) = writes m + < 2 m (all copies) < 3 m ⟹ \overset{c}{^} = \frac{T ( m )}{m} < 3 = O (1) .$

Here $T (m)$ is the total real work for the whole sequence, and $\overset{c}{^}$ (read "c-hat") is the amortized cost — the total shared evenly across the $m$ pushes.

PICTURE:

Step 5 — Accounting method: prepay with coins

WHAT: each newly pushed item arrives holding 3 coins. It spends 1 to write itself into its box, then keeps 2 coins in reserve.

Intuition WHY exactly 2 saved coins — the precise counting (not hand-waving)

Follow the array from just after a doubling to the next one. Right after we grow to capacity $s = 2 n$ , the array holds $n$ items and is half full. It fills up as we push $n$ more items, until $n^{'} = s = 2 n$ items — then the next copy fires and must move all $2 n$ items.

Who pays for those $2 n$ moves? Only the pushes done since the last doubling — and there are exactly $n$ of them (we went from $n$ items to $2 n$ items). If each saved just 1 coin, we would bank only $n$ coins to pay a copy of cost $2 n$ — not enough, the bank goes negative. That is precisely why 1 coin per push fails.

With 2 coins saved per push we bank $2 \times n = 2 n$ coins over that fill-up window, exactly matching the $2 n$ -item copy. So the two coins split naturally: one coin moves the item that saved it, and the other coin moves one of the $n$ items that were already present at the last doubling and whose own reserves were spent in the previous copy. Every copy is fully prepaid; the bank never dips below zero. ✓

PICTURE:

Step 6 — Potential method: energy stored in the structure

We now walk all three regimes of a push, using the piecewise $Φ$ above.

WHAT — Case A: cheap push that stays at/above half full (before: $n \geq s /2$ , after: still $\geq s /2$ , capacity $s$ unchanged): $\overset{c}{^} = c_{i} 1 + [Φ after 2 (n + 1) - s] - [Φ before 2 n - s] = 1 + 2 = 3.$ The real write costs $1$ ; potential rises by $2$ (we banked energy). Total $3$ .

WHAT — Case B: cheap push while below half full (before: $n < s /2$ ). Here $Φ_{before} = 0$ . After the push $n \to n + 1$ ; potential is either still $0$ (if $n + 1 < s /2$ ) or becomes $2 (n + 1) - s$ (if it just reached half full). In the stays-below sub-case: $\overset{c}{^} = c_{i} 1 + [Φ after 0] - [Φ before 0] = 1 \leq 3.$ Even cheaper than $3$ — the bound $\overset{c}{^} \leq 3$ still holds. In the just-crosses-half sub-case, $Φ$ jumps from $0$ to $2 (n + 1) - s$ . Because we just reached $n + 1 = ⌈ s /2 ⌉$ , that jump is at most $2$ , so $\overset{c}{^} \leq 1 + 2 = 3$ again. This is exactly why the "symmetric" branch is simply $Φ = 0$ : setting the below-half potential to zero can only make the drop into a copy larger and the rises smaller, so every push still satisfies $\overset{c}{^} \leq 3$ , and the telescoping sum (below) is untouched.

WHAT — Case C: expensive resizing push (full: before-state $n = s$ so $Φ_{before} = 2 n - s = n$ ; copy $n$ , then $s \to 2 s$ , $n \to n + 1$ , and now $n + 1$ vs new capacity $2 s = 2 n$ gives $n + 1 \geq s = n$ ? we have $n + 1 \geq (2 s) /2 = s = n$ , true, so use the $2 n - s$ branch): $\overset{c}{^} = c_{i} : copy n + write 1 (n + 1) + [Φ after = 2 2 (n + 1) - 2 s] - [Φ before = n 2 n - s] = (n + 1) + (2 - n) = 3.$ The huge real cost $n + 1$ is cancelled by the potential crashing from $n$ down to $2$ . The stored spring released exactly enough energy to pay for the copy.

All three cases give $\overset{c}{^} \leq 3 = O (1)$ . ✓ — same answer as the aggregate and accounting methods.

PICTURE:

Step 7 — The degenerate & edge cases (never leave a gap)

The very first push ( $n_{0} = 0$ , $s_{0} = 1$ ): the array is not full ( $0 < 1$ ), so the first push is a cheap write into the single box, cost $1$ . No copy. $Φ$ starts at $0$ (below half full), stays consistent with Step 6 Case B.
$m$ not a power of two (e.g. $m = 1000$ , so $k = ⌊ lo g_{2} 1000 ⌋ = 9$ ): the last resize happened at $2^{k} = 512 \leq 1000$ , and we simply stop mid-strip. The sum $1 + 2 + \dots + 2^{k} < 2 m$ still holds — the geometric bound never needed $m$ to be a nice number.
Empty sequence ( $m = 0$ ): total cost $0$ , no operations, bound holds vacuously.
A push right after a resize (deep below half full): immediately after doubling, $n$ is small relative to the new $s$ , so the raw expression $2 n - s$ could momentarily be negative. This is exactly the region where the piecewise definition uses $Φ = 0$ instead (Step 6 Case B), never a negative number. We proved there that $\overset{c}{^} \leq 3$ in every below-half sub-case, so nothing breaks.

WHAT: the figure lines up all four edge cases as mini-strips with their costs labelled, so you can confirm each one obeys $\overset{c}{^} \leq 3$ (or costs nothing).

PICTURE:

The one-picture summary

This final figure stacks all three viewpoints of the same sequence of pushes:

Aggregate (bottom): rare tall copy-bars whose total height is under $2 m$ .
Accounting (middle): each push carrying 3 coins, the piggy bank never emptying below zero.
Potential (top): the energy $Φ = 2 n - s$ (or $0$ below half full) sawtoothing upward on cheap pushes, then crashing to pay each copy.

All three cross the finish line at the same flat line $\overset{c}{^} = 3 = O (1)$ .

Recall Feynman retelling — the whole walkthrough in plain words

You have a row of boxes, starting with just one empty box ( $n_{0} = 0$ , $s_{0} = 1$ ). Usually you just plop your next thing into the next empty box — one unit of effort, done. But every so often you run out of boxes, and then you must buy a strip twice as long and carry everything over — a big, sweaty job. It feels like pushing is expensive.

But watch how often the sweaty job happens: only when you hit sizes $1, 2, 4, 8, 16 \dots$ — each time farther apart than the last. Add up all the carrying you ever do and it comes to less than twice the number of pushes. So spread across everything, each push cost you about 3 units, flat. That's the aggregate view: add it all, divide.

Prefer coins? Charge yourself 3 coins per push, spend 1, save 2. Between one doubling and the next you push $n$ items and bank $2 n$ coins — exactly what the next copy of $2 n$ items costs. One coin per push would only bank $n$ and fall short; that's why it must be two. The bank never goes negative. That's accounting.

Prefer physics? Picture a spring that you wind up 2 notches on every cheap push once the array is half full (and just leave slack — zero energy — while it's still emptier than half). When the array fills, the spring is wound to $n$ notches — and releasing it delivers precisely the energy needed to copy the items. That's potential: $\overset{c}{^} = c + ΔΦ$ , and the crash in $Φ$ eats the big cost.

Three stories, one truth: occasionally huge, always cheap on average, guaranteed.

Connections

Dynamic Arrays / Table Doubling — the structure whose growth we drew here.
Geometric Series — the $1 + 2 + 4 + \dots < 2 m$ engine behind Step 4.
Big-O, Big-Omega, Big-Theta — $\overset{c}{^} = O (1)$ is still asymptotic notation.
Disjoint Set Union (Union-Find), Splay Trees, Fibonacci Heaps — where the potential method of Step 6 becomes indispensable.
Parent topic ↑