Amortized Analysis

March 2026 · 22 min read

Some operations are expensive sometimes but cheap most of the time. Worst-case analysis overestimates their cost. Amortized analysis gives the average cost per operation over a worst-case sequence of operations.

Key distinction: Amortized ≠ average case. Average case assumes a probability distribution on inputs. Amortized analysis considers the worst-case sequence of $n$ operations and divides total cost by $n$. No randomness involved.

Motivating Example: Dynamic Array (std::vector)

A dynamic array doubles its capacity when full. Most push_back calls are $O(1)$ (just append). But when the array is full, we allocate a new array of double the size and copy everything: $O(n)$.

Worst case per operation: $O(n)$. But is it really $O(n)$ per operation on average over a sequence?

The sequence for n = 8 pushes

Push #	Size before	Capacity	Resize?	Cost
1	0	1	Yes (0→1)	1
2	1	1	Yes (1→2)	1 + 1 = 2
3	2	2	Yes (2→4)	1 + 2 = 3
4	3	4	No	1
5	4	4	Yes (4→8)	1 + 4 = 5
6	5	8	No	1
7	6	8	No	1
8	7	8	No	1

Total cost: $1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 = 15$. Over 8 operations: $15 / 8 < 2$. Amortized cost per push: $O(1)$!

Method 1: Aggregate Analysis

Compute the total cost of $n$ operations, then divide by $n$.

Dynamic array: total cost of $n$ pushes

Non-resize cost: $n$ (1 per push). Resize costs: copies happen when size hits $1, 2, 4, 8, \ldots, 2^k$ where $2^k \leq n$. Total copy cost:

$$\sum_{i=0}^{\lfloor \log_2 n \rfloor} 2^i = 2^{\lfloor \log_2 n \rfloor + 1} - 1 < 2n$$

Total cost: $n + 2n = 3n$. Amortized cost per operation: $3n / n = 3 = O(1)$. ✔

Method 2: Accounting (Banker's) Method

Assign an amortized cost (a "charge") to each operation that's higher than the actual cost. The excess is stored as credit on data structure elements. When an expensive operation happens, pay with saved credits.

Dynamic array: charge 3 per push

Actual cost: 1 (no resize) or $1 + k$ (resize: copy $k$ elements + insert).
Amortized charge: 3 per push.

Of the $3 charged:

$1$ pays for the push itself.
$1$ is saved to pay for copying this element in a future resize.
$1$ is saved to pay for copying an older element that was already there before the last resize.

When a resize happens, we copy $n/2$ elements (the old half) and $n/2$ elements (the new half since last resize). Each new element since the last resize has $2$ credits. Total credits available: $2 \times (n/2) = n$. Actual copy cost: $n$. Credits exactly cover it. ✔

Invariant: Credit is always $\geq 0$ (we never "borrow" against future operations). This proves the amortized cost is a valid upper bound on total cost.

Method 3: Potential Method

Define a potential function $\Phi(D_i)$ that maps data structure state $D_i$ (after the $i$-th operation) to a non-negative number. The amortized cost of operation $i$ is:

$$\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$$

Telescoping over $n$ operations:

$$\sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0)$$

If $\Phi(D_n) \geq \Phi(D_0)$ (which is guaranteed if $\Phi \geq 0$ and $\Phi(D_0) = 0$), then $\sum \hat{c}_i \geq \sum c_i$, so amortized costs are valid upper bounds.

Dynamic array with potential method

Let $\Phi = 2 \cdot \text{size} - \text{capacity}$. After construction: $\Phi(D_0) = 0$.

Case 1: No resize. $c_i = 1$. Size increases by 1. $\Delta\Phi = 2$.

$$\hat{c}_i = 1 + 2 = 3$$

Case 2: Resize. If size was $m$ and capacity was $m$, we copy $m$ elements (cost $m$) and insert ($+1$). New capacity = $2m$. New size = $m + 1$.

$$\hat{c}_i = (m + 1) + [2(m+1) - 2m] - [2m - m] = (m+1) + 2 - m = 3$$

In both cases, amortized cost = $3 = O(1)$. ✔

Case Study: Union-Find

Union-Find with union by rank and path compression achieves $O(\alpha(n))$ amortized per operation, where $\alpha$ is the inverse Ackermann function, effectively constant (≤ 4 for any practical $n$).

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // path compression
    return parent[x];
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) swap(rx, ry);
    parent[ry] = rx;                   // union by rank
    if (rank[rx] == rank[ry]) rank[rx]++;
}

The proof uses a sophisticated potential function based on the rank structure. The key insight: path compression flattens the tree, making future find operations cheaper. Each expensive find (following a long path) permanently shortens that path, paying for future operations.

Classic Example: Binary Counter

Incrementing a $k$-bit binary counter. Each increment can flip up to $k$ bits (worst case)

Aggregate analysis

Bit 0 flips every increment: $n$ flips total.
Bit 1 flips every 2nd increment: $n/2$ flips.
Bit $i$ flips every $2^i$ increments: $n/2^i$ flips.

$$\text{Total flips} = \sum_{i=0}^{k-1} \frac{n}{2^i} < 2n$$

Amortized cost per increment: $2n / n = 2 = O(1)$. ✔

When to Use Amortized Analysis

An operation is expensive sometimes but cleans up / restructures so future operations are cheap.
The data structure has internal state that changes over time (capacity, tree shape, etc.).
Worst-case per-operation analysis gives a misleadingly high bound.

Data Structure	Operation	Worst Case	Amortized
Dynamic array	push_back	$O(n)$	$O(1)$
Hash table	insert	$O(n)$	$O(1)$
Union-Find	find/union	$O(\log n)$	$O(\alpha(n))$
Splay tree	any op	$O(n)$	$O(\log n)$
Fibonacci heap	decrease-key	$O(n)$	$O(1)$

Summary

Amortized analysis gives the average cost per operation over a worst-case sequence. Not probabilistic.
Aggregate method: Total cost / number of operations. Simplest.
Accounting method: Charge more than actual cost; save credits for expensive operations.
Potential method: Define $\Phi$ mapping state to a number. $\hat{c}_i = c_i + \Delta\Phi$. Most general.
The dynamic array's push_back is $O(1)$ amortized despite $O(n)$ worst case.