Amortized analysis — aggregate, accounting, potential methods: Worked examples

The scenario matrix

Every amortized problem is really a combination of a structure, a cost pattern, and an edge condition. The table lists every cell we must cover; the "Example" column tells you which worked example hits it.

Here $m$ = the total number of operations in the sequence we analyse (pushes, increments, log lines — whatever the structure's basic operation is). It is the single most important symbol on this page: amortized cost is cost averaged over these $m$ operations, so $m$ appears in every bound.

Cell	What makes it tricky	Example
A. Cheap-then-rare-expensive	usual $O (1)$ , occasional $O (n)$	Ex 1 (aggregate), Ex 2 (potential)
B. Bit-cascade cost	one op flips many bits	Ex 3 (binary counter)
C. Zero / degenerate input	$m = 0$ , first op, empty structure	Ex 4
D. Both-ends expensive	grow and shrink both cost $O (n)$	Ex 5 (shrinking array — the trap)
E. Wrong potential	picking $Φ$ that breaks a rule	Ex 6 (steel-man)
F. Non-uniform op mix	different ops, aggregate too weak	Ex 7 (stack with multipop)
G. Limiting behaviour	what happens as $m \to \infty$	Ex 8
H. Real-world word problem	translate a story into $c_{i}, Φ$	Ex 9 (server log flush)
I. Exam twist	doubling and halving thresholds	Ex 10

Before any example, we re-earn every symbol used on this page — do not assume the parent.

A + limiting: the aggregate baseline

Worked example

Ex 1 — Cell A. $m$ pushes into a doubling array, aggregate method. Statement: Start capacity 1. Push $m = 1000$ elements. What is the total work and the amortized cost per push?

Forecast: Guess first — is the total closer to $1000$ , $3000$ , or $1, 000, 000$ ? (The naive "each push is $O (n)$ " scream says a million.)

Cheap writes. Every push writes one element: $1000$ writes. Why this step? Separate the always-happens cost from the rare cost so we can sum them independently.
Copy events. Copies happen when size hits a power of two: $1, 2, 4, \dots, 512$ . Total copied $= 1 + 2 + 4 + \dots + 512$ . Why this step? Copies are the only expensive part; isolate their sizes.
Sum the geometric series (see Geometric Series): $1 + 2 + \dots + 512 = 2^{10} - 1 = 1023 < 2 m = 2000$ . Why this step? The doubling makes copy sizes a geometric progression whose sum is $< 2 m$ — this is the whole reason the expense stays bounded.
Total $T (m) = 1000 + 1023 = 2023$ . Amortized $= 2023/1000 = 2.023 \leq 3$ .

Verify: $T (m) \leq m + 2 m = 3 m = 3000$ . We got $2023 \leq 3000$ . ✓ And $2.023 = O (1)$ — constant per push, no $n$ in sight.

The figure below draws the first $m = 20$ pushes — a smaller, readable slice of the same $m = 1000$ sequence (the pattern just repeats with taller, rarer spikes as you go further right, so 20 is enough to see the shape). Read it left to right: mint bars are the height-1 cheap writes that happen on every push, and the coral spikes are the rare copies at sizes $1, 2, 4, 8, 16$ . Notice the coral spikes get taller but further apart — that spreading-out is exactly why the dashed lavender line at height 3 (the amortized charge) sits comfortably above the average, at $m = 20$ just as at $m = 1000$ .

Figure — Amortized analysis — aggregate, accounting, potential methods

Recall Why does the geometric sum beat the naive fear?

Naive fear counts the $O (n)$ copy every push. ::: But that copy happens only once per doubling; the gaps between doublings grow, so averaged cost is constant.

A via potential — same answer, cleaner algebra

Worked example

Ex 2 — Cell A (potential). Re-derive Ex 1 using $Φ = 2 n - s$ . Statement: Confirm $\overset{c}{^} = 3$ for both a normal push and the copy-push, using potential. (Recall $n$ = elements stored, $s$ = capacity.)

Forecast: Which push should have its huge real cost cancelled by a potential drop — the normal one or the resizing one?

Normal push ( $n \to n + 1$ , capacity $s$ fixed): $ΔΦ = [2 (n + 1) - s] - [2 n - s] = 2$ . Why this step? A cheap op should save energy (raise $Φ$ ) so future copies are prepaid — this is Rule 3 for cheap ops.
$\overset{c}{^} = c_{i} + ΔΦ = 1 + 2 = 3$ .
Resizing push at $n = s$ : actual $c_{i} = n + 1$ (copy $n$ , insert $1$ ). Before $Φ = 2 n - s = 2 n - n = n$ ; after (capacity $2 s = 2 n$ , size $n + 1$ ) $Φ = 2 (n + 1) - 2 n = 2$ . Why this step? The expensive op should release energy: $ΔΦ = 2 - n$ (Rule 3 for expensive ops).
$\overset{c}{^} = (n + 1) + (2 - n) = 3$ . Why this step? Add actual cost and $ΔΦ$ (the master equation) so the huge real cost $n + 1$ is cancelled by the potential drop $2 - n$ , leaving the constant $3$ — this is the whole payoff of choosing $Φ = 2 n - s$ .

Verify: Both cases give exactly $3$ , matching aggregate's $\leq 3$ . Take $n = 512$ (the copy at $m = 513$ ): $c_{i} = 513$ , $ΔΦ = 2 - 512 = - 510$ , $\overset{c}{^} = 513 - 510 = 3$ . ✓ The $510$ of stored energy paid the copy.

The next figure plots the potential $Φ = 2 n - s$ as the array fills. Follow the lavender curve: on each ordinary push it climbs by $2$ (energy saved into the shaded well below it), building up a tall reserve. Then, at each doubling, the coral arrow marks the moment the curve plunges — that vertical drop is the stored energy being spent to pay the copy, leaving only $Φ = 2$ behind. The saw-tooth shape is the piggy-bank filling and smashing.

B — the bit cascade

Worked example

Ex 3 — Cell B. Increment an 8-bit counter from $0$ up $256$ times. Total bit-flips? Statement: Each increment costs the number of bits flipped. Find total flips over $m = 256$ increments and the amortized cost.

Forecast: One increment can flip all 8 bits ( $01111111 \to 10000000$ flips... actually $011... \to 100...$ ). Does that make the average near 8, or near 2?

Bit 0 (the ones place) flips every increment: $256$ flips. Why this step? Count flips per bit instead of per increment — each bit has a clean period.
Bit 1 flips every 2 increments: $256/2 = 128$ . Bit 2: $256/4 = 64$ . Continue. Why this step? Bit $b$ toggles every $2^{b}$ increments — a geometric pattern again.
Total flips $= 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 = 510 < 2 \cdot 256 = 512$ . Why this step? Sum of $\sum_{b \geq 0} m / 2^{b} < 2 m$ — the same $< 2 m$ geometric bound.
Amortized $= 510/256 \approx 1.99 \leq 2 = O (1)$ . Why this step? Divide total work by the number of operations $m$ — that is the definition of amortized cost, and the constant result (no $k$ , no $n$ ) confirms $O (1)$ .

Verify: Accounting cross-check — charge $2 per increment: $1 to set a bit $0 \to 1$ , $1 stored on it to pay its future $1 \to 0$ carry. $256$ increments $\times \$ 2 = $512 \ge 510$ actual. ✓

C — zero and degenerate inputs

Worked example

Ex 4 — Cell C. Edge cases: $m = 0$ , the very first push, and an empty pop. (As above, $n$ = elements, $s$ = capacity, $m$ = number of operations.) Statement: (a) What does amortized analysis say for $m = 0$ ? (b) First push into empty array of capacity 1. (c) Pop from empty structure.

Forecast: Does the amortized bound $\leq 3 m$ break at $m = 0$ ?

(a) $m = 0$ : $T (0) = 0 \leq 3 \cdot 0 = 0$ . The bound holds with equality and vacuously — no operations, no cost. Why this step? Always test the boundary of the summation; $\sum$ over empty range is $0$ .
(b) First push: $n : 0 \to 1$ , capacity already $1$ , no resize. Naively plugging $n = 0, s = 1$ gives $Φ_{0} = 2 (0) - 1 = - 1$ , which is negative — forbidden. Why this step? The formula $Φ = 2 n - s$ only produces $Φ \geq 0$ once $n \geq s /2$ (because $2 n \geq s ⟺ 2 n - s \geq 0$ ). Before the box is half-full, $2 n - s$ dips below zero, so the raw formula is outside its valid domain there. The standard fix is to define $Φ$ piecewise: use $Φ = 2 n - s$ only when $n \geq s /2$ , and pin $Φ = 0$ on the empty start. This respects Rule 1 ( $Φ (D_{0}) = 0$ ) and Rule 2 ( $Φ \geq 0$ ).
With $Φ_{0} = 0$ , $Φ_{1} = 2 (1) - 1 = 1$ (now $n = 1 \geq s /2 = 0.5$ , so the formula is valid): $\overset{c}{^} = 1 + (1 - 0) = 2 \leq 3$ . ✓
(c) Empty pop: $c = 0$ (nothing to remove) and $Φ$ unchanged, so $\overset{c}{^} = 0$ . A degenerate op is free and never breaks the bound. Why this step? We must confirm the degenerate operation still satisfies $\overset{c}{^} \geq 0$ ; a no-op has zero actual cost and zero $ΔΦ$ , so its amortized cost is $0$ , keeping the running total honest ( $\sum \overset{c}{^} \geq \sum c$ ).

Verify: $T (0) = 0$ , first-push $\overset{c}{^} = 2 \leq 3$ , empty-pop $\overset{c}{^} = 0 \geq 0$ . All three edge cases respect $\sum \overset{c}{^} \geq \sum c \geq 0$ . ✓

D — the shrinking trap (both ends expensive)

Worked example

Ex 5 — Cell D. A naive resizable array that doubles when full and halves when quarter-full. Show the bad threshold and the good fix, with the full $ΔΦ$ derivation. (Reminder: $n$ = elements, $s$ = capacity.) Statement: Compare shrink-at-half vs shrink-at-quarter, and verify $O (1)$ with $Φ = ∣2 n - s ∣$ .

Forecast: If we halve as soon as the array is half-empty, what happens to a push,pop,push,pop,... sequence right at capacity?

Bad rule (halve when $n$ drops to $s /2$ ): at capacity $s$ , push → box full → resize up (copy $s$ ), then pop → now $n = s /2$ → immediately resize down (copy $s /2$ ), then push again → resize up... Why this step? Sit exactly on the threshold and alternate — this is the adversary's favourite input.
Each of these ops costs $Θ (s) = Θ (n)$ , and it repeats forever: amortized $= Θ (n)$ , not $O (1)$ . The method didn't fail; the design did (no buffer between the two thresholds). Why this step? Amortized $O (1)$ needs expensive events to be rare; touching a resize every op kills rarity.
Good rule (halve when $n$ drops to $s /4$ ). Use potential $Φ = ∣2 n - s ∣$ (the absolute value grows as $n$ leaves the comfortable middle $n = s /2$ , in either direction). Check the rules against the true starting state $n = 0, s = 1$ : there $Φ = ∣2 \cdot 0 - 1∣ = 1 \neq = 0$ , so raw $∣2 n - s ∣$ violates Rule 1. Fix it exactly as in Ex 4 — pin $Φ (D_{0}) = 0$ on the empty start and use $Φ = ∣2 n - s ∣$ once the structure is populated (from the first push onward the array settles to $n \approx s /2$ , where $Φ$ is small and the formula behaves). Rule 2 ( $Φ \geq 0$ ) holds automatically because $∣ \cdot ∣ \geq 0$ . With this pinning the "comfortable middle" $n = s /2$ gives $Φ = 0$ , matching the intuition that a half-full box stores no resize-energy. Why this step? We need a potential that stores energy near both the "too full" and "too empty" walls, so both a doubling and a halving can be prepaid — but we must reconcile it with the genuine $n = 0, s = 1$ start, not just assume $n = s /2$ .
Ordinary push or pop (no resize): $n$ moves by $1$ , so $∣2 n - s ∣$ moves by at most $2$ . Thus $ΔΦ \leq 2$ and $\overset{c}{^} = 1 + ΔΦ \leq 1 + 2 = 3$ . Why this step? Bound the common case first — its potential swing is tiny.
Doubling push at $n = s$ (box full): actual $c_{i} = s + 1$ (copy $s$ , insert 1). Before: $Φ = ∣2 s - s ∣ = s$ . After ( $s^{'} = 2 s$ , $n = s + 1$ ): $Φ = ∣2 (s + 1) - 2 s ∣ = 2$ . So $ΔΦ = 2 - s$ , and $\overset{c}{^} = (s + 1) + (2 - s) = 3$ . Why this step? The reserve $Φ = s$ built up while filling gets released, cancelling the $s + 1$ copy (Rule 3 for expensive ops).
Halving pop at $n = s /4$ : this pop first removes one element, dropping the count to $n^{'} = s /4 - 1$ survivors, then copies those survivors into a half-size box. So actual $c_{i} = (s /4 - 1) + 1 = s /4$ — the $- 1$ is the removed element, the final $+ 1$ is the pop's own bookkeeping; I count the survivors copied, not the removed element. Before: $Φ = ∣2 (s /4) - s ∣ = ∣ s /2 - s ∣ = s /2$ . After ( $s^{'} = s /2$ , $n = s /4 - 1$ ): $Φ = ∣2 (s /4 - 1) - s /2∣ = ∣ s /2 - 2 - s /2∣ = 2$ . So $ΔΦ = 2 - s /2$ , and $\overset{c}{^} = (s /4) + (2 - s /2) = 2 - s /4 \leq 3$ . Why this step? The reserve built up while emptying toward the quarter-wall pays the shrink, symmetric to step 5; being explicit about the off-by-one (survivors $= s /4 - 1$ , work counted $= s /4$ ) prevents mis-counting the copy.

Verify: Bad rule over $m$ alternating ops at size $n$ : total $\approx m \cdot (n /2) = Θ (mn)$ , so amortized $Θ (n)$ ✗. Good rule: ordinary $\overset{c}{^} \leq 3$ , doubling $\overset{c}{^} = 3$ , halving $\overset{c}{^} = 2 - s /4 \leq 3$ — all $O (1)$ . ✓ (Take $s = 100$ : double gives $3$ , halve at $n = 25$ gives $2 - 25 = - 23$ , meaning that op stores net energy — still valid because $Φ$ stays $\geq 0$ .)

E — a broken potential (steel-man)

Worked example

Ex 6 — Cell E. "Let me use $Φ = n$ for the doubling array." Why does this fail? Statement: Test $Φ = n$ (just the element count) on the resizing push, and see which rule breaks.

Forecast: $Φ = n$ satisfies Rule 2 ( $n \geq 0$ ) and Rule 1 ( $Φ (D_{0}) = 0$ ). So it must work, right?

Normal push: $ΔΦ = (n + 1) - n = 1$ , so $\overset{c}{^} = 1 + 1 = 2$ . Looks fine so far. Why this step? Check the cheap op first; it passes, luring you in.
Resizing push at $n = s$ : actual $c_{i} = n + 1$ . $Φ$ before $= n$ , after $= n + 1$ . $ΔΦ = + 1$ . Why this step? The expensive op must drop $Φ$ to cancel its cost — here $Φ$ rose, violating Rule 3.
$\overset{c}{^} = (n + 1) + 1 = n + 2 = O (n)$ . The potential never stored the copy money, so the amortized bound blows up with $n$ . Why this step? Rule 3 (expensive ops drop $Φ$ ) is broken: $Φ = n$ has no capacity ( $s$ ) term, so it can't even sense that the box is full — it rises monotonically and never releases a reserve.
The fix is exactly the parent's $Φ = 2 n - s$ : the $- s$ term drops by $s$ on a resize (capacity jumps from $n$ to $2 n$ ), releasing $s$ units of stored energy — which is why Ex 2 got the clean $\overset{c}{^} = 3$ . The lesson: Rules 1 and 2 are necessary but not sufficient; without Rule 3 a "legal" potential can still give a useless (large) bound. Why this step? We close the steel-man by naming the specific structural fix (add the $- s$ term) and the general moral (Rule 3 is the one that makes the bound tight), so the reader leaves with both the counterexample and its cure.

Verify: With $Φ = n$ , $n = 512$ : $\overset{c}{^} = 512 + 2 = 514 = O (n)$ ✗. With $Φ = 2 n - s$ : $\overset{c}{^} = 3$ ✓. Rules 1 and 2 alone are not enough — Rule 3 is the one that makes the bound tight.

F — non-uniform operations (aggregate shines here)

Worked example

Ex 7 — Cell F. Stack with push, pop, and multipop(k) (pop up to $k$ items). $m$ operations, amortized cost? Statement: multipop(k) pops $min (k, size)$ items and costs $min (k, size)$ (plus $O (1)$ overhead to invoke it). A single multipop can be $O (n)$ . Find amortized cost over any $m$ ops.

Forecast: One multipop can pop everything — $O (n)$ . Aggregate over $m$ ops: near $O (n)$ or $O (1)$ each?

Split each op's cost into (i) a fixed $O (1)$ overhead and (ii) per-item work. Even a multipop(k) on an empty stack still costs the fixed overhead of calling it, but pops zero items — the $min (k, size)$ correctly charges only for items that actually exist. Why this step? Partial multipops (when $k$ exceeds the current size) must not be over-counted; $min (k, size)$ handles that automatically, and we account the call cost separately.
Key invariant for the per-item work: every element is popped at most once, and it must be pushed before it is popped. So the total number of pop-actions (single pop + all items removed by every multipop) $\leq$ the total number of pushes. Why this step? You cannot remove more items than you ever inserted — this caps all per-item work by the push count, regardless of how the pops are grouped.
Aggregate the two parts. With $m$ operations: at most $m$ of them are pushes, so per-item work $\leq m$ (each pushed item accounts for one push + at most one pop $= 2$ touches), and the fixed overhead is $\leq c_{0} \cdot m$ for a constant $c_{0}$ . Total work $\leq 2 m + c_{0} m = O (m)$ . Why this step? Aggregate counts total object-touches plus a constant per call — both are $O (m)$ .
Amortized $= O (m) / m = O (1)$ per operation — even for multipop!

Verify: Sequence: push $\times 100$ , then one multipop(100). Per-item work $= 100$ (pushes) $+ 100$ (items popped) $= 200$ ; ops $= 101$ ; per op $= 200/101 \approx 1.98 = O (1)$ . ✓ A multipop(500) on that same 100-element stack would pop only $min (500, 100) = 100$ items — the giant $k$ costs nothing extra beyond what exists.

G — limiting behaviour

H — real-world word problem

Worked example

Ex 9 — Cell H. A server buffers log lines in memory and flushes to disk whenever the buffer hits a power-of-two size, rewriting the whole file. $m$ log lines arrive. Cost per flush = current buffer size (rewrite). Amortized cost per log line? Statement: Translate the story into $c_{i}$ and find amortized cost.

Forecast: Rewriting the whole file sounds like $O (n)$ per flush — is logging expensive on average?

Model it: appending a line = 1 unit; a flush at size $2^{j}$ = $2^{j}$ units (rewrite). Here the buffer size plays the role of $n$ (elements stored). Why this step? Map "rewrite the file" onto the same copy-cost pattern as table doubling.
Flushes occur at sizes $1, 2, 4, \dots \leq m$ : total flush cost $= 1 + 2 + \dots + 2^{k} < 2 m$ . Why this step? Identical geometric series — the story is table doubling in disguise.
Total $= m (appends) + < 2 m (flushes) < 3 m$ .
Amortized $= < 3$ units per log line $= O (1)$ .

Verify: $m = 1000$ lines: appends $= 1000$ , flushes $= 1 + 2 + \dots + 512 = 1023$ , total $= 2023$ , per line $= 2.023 < 3$ . ✓ Logging is $O (1)$ amortized despite full rewrites.

I — exam twist: combined thresholds

Worked example

Ex 10 — Cell I. Exam question: a deque doubles at full and halves at quarter-full. Using $Φ = 2 ∣ n - s /2∣$ , prove push/pop are $O (1)$ amortized in the worst case. (Reminder: $n$ = elements, $s$ = capacity; note $2∣ n - s /2∣ = ∣2 n - s ∣$ , the same potential as Ex 5.) Statement: Verify $\overset{c}{^} = O (1)$ for the harder both-directions structure.

Forecast: With two thresholds, can one potential guard both a doubling and a halving?

Sanity of $Φ$ : $Φ = 2∣ n - s /2∣ \geq 0$ always (Rule 2), and (as in Ex 5) we pin $Φ (D_{0}) = 0$ on the empty start so Rule 1 holds; once populated, $n = s /2$ gives $Φ = 0$ , the resting state. Why this step? Never analyse cost before confirming $Φ \geq 0$ and starts at $0$ .
Non-resizing op: $n$ changes by $1$ , so $∣ n - s /2∣$ changes by at most $1$ , giving $∣ΔΦ∣ \leq 2$ . Then $\overset{c}{^} = 1 + ΔΦ \leq 1 + 2 = 3$ . Why this step? Bound the potential swing of the common case.
Doubling push ( $n = s$ ): before $Φ = 2∣ s - s /2∣ = 2 \cdot s /2 = s$ ; after ( $s^{'} = 2 s$ , $n = s + 1$ ) $Φ = 2∣ s + 1 - s ∣ = 2$ . So $ΔΦ = 2 - s$ ; $c_{i} = s + 1$ ; $\overset{c}{^} = (s + 1) + (2 - s) = 3$ . Why this step? The $Φ$ dropped by $s - 2$ , cancelling the $s + 1$ copy (Rule 3).
Halving pop ( $n = s /4$ ): as in Ex 5, one element is removed leaving $s /4 - 1$ survivors to copy, so $c_{i} = s /4$ . Before $Φ = 2∣ s /4 - s /2∣ = 2 \cdot s /4 = s /2$ ; after ( $s^{'} = s /2$ , $n = s /4 - 1$ ) $Φ = 2∣ (s /4 - 1) - s /4∣ = 2$ . So $ΔΦ = 2 - s /2$ ; $\overset{c}{^} = (s /4) + (2 - s /2) = 2 - s /4 \leq 3$ . Why this step? Same energy-release principle in the shrink direction, symmetric to step 3, with the same explicit survivor count.

Verify: Take $s = 100$ . Double: $\overset{c}{^} = (100 + 1) + (2 - 100) = 3$ ✓. Halve at $n = 25$ , $s = 100$ : $\overset{c}{^} = 25 + (2 - 50) = 25 - 48 = - 23$ — a negative amortized cost for a single op is fine; it means that op stored net energy rather than spending it. What guarantees honesty overall: $Φ \geq 0$ throughout, so $\sum \overset{c}{^} \geq \sum c$ . Non-resizing $\overset{c}{^} \leq 3$ , resizing $\overset{c}{^} \leq 3$ — all $O (1)$ . ✓

Connections

Dynamic Arrays / Table Doubling — Ex 1, 2, 4, 5, 10 all live here.
Geometric Series — the $1 + 2 + \dots + 2^{k} < 2 m$ engine behind every example.
Big-O, Big-Omega, Big-Theta — every $\overset{c}{^}$ ends in $O (1)$ or $O (n)$ asymptotics.
Disjoint Set Union (Union-Find), Splay Trees, Fibonacci Heaps — advanced structures where the potential method of Ex 6/10 is the only practical tool.