Prerequisite:

Worst-case per-operation analysis is often too pessimistic. When a sequence of operations is interleaved so that expensive ones are rare, the average cost per operation can be much lower than the single-operation worst case. Amortized analysis makes this precise. It is not an approximation - it is an exact statement about a sequence of $n$ operations.

Why Worst-Case Per Operation Is Too Pessimistic

Consider a dynamic array supporting push. Most pushes cost $O(1)$. Every so often, when the array is full, a push triggers a resize: copy all $k$ elements to a new array of size $2k$. The resize costs $O(k)$ - but it only happens once every $k$ pushes. Declaring the worst-case cost per push as $O(n)$ would make dynamic arrays sound no better than linked lists. Amortized analysis recovers the true picture: $O(1)$ per push on average over any sequence.

There are three standard techniques: aggregate, accounting, and potential. All three give the same final bound; they differ in what intuition they expose.

Aggregate Method

The aggregate method computes the total cost $T(n)$ of any sequence of $n$ operations, then defines the amortized cost per operation as $T(n)/n$.

Dynamic array doubling: Consider $n$ pushes starting from an empty array of capacity 1. Non-resize pushes cost 1 each. Resize at capacity $k$ costs $k$ (copying $k$ elements). Resizes happen at sizes $1, 2, 4, 8, \ldots, 2^{\lfloor \log n \rfloor}$. Total resize cost:

$$\sum_{i=0}^{\lfloor \log n \rfloor} 2^i < 2n$$

Total cost of $n$ pushes: $n + 2n = 3n = O(n)$. Amortized cost per push: $O(n)/n = O(1)$.

Accounting Method

The accounting method assigns each operation a credit. Operations that are charged more than their actual cost store the surplus as credit on data structure objects. The invariant is that stored credit is always $\geq 0$ - we never “borrow from the future.”

Dynamic array: charge each push $3$ credits ($1$ to pay for the push itself, $2$ saved for future). When a resize occurs on an array of capacity $k$ (currently half-full with $k/2$ elements):

  • The $k/2$ elements inserted since the last resize each stored 2 credits.
  • Total stored credit: $k$ - exactly enough to pay for copying all $k$ elements.

The invariant holds: credit never goes negative. Since each push is charged $O(1)$ credits, amortized cost per push is $O(1)$.

Potential Method

The potential method is the most general and the most useful for complex data structures. Define a potential function $\Phi : \text{DataStructure} \to \mathbb{R}_{\geq 0}$ mapping each state of the data structure to a non-negative real. The amortized cost of operation $i$ is:

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

where $c_i$ is the actual cost and $D_i$ is the state after operation $i$. Summing over all $n$ operations:

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

Since $\Phi(D_n) \geq 0$ and $\Phi(D_0) = 0$ (by convention), we get:

$$\sum_{i=1}^{n} c_i \leq \sum_{i=1}^{n} \hat{c}_i$$

So if we can bound $\hat{c}_i = O(f(n))$ for all $i$, then the total actual cost is $O(n \cdot f(n))$. The amortized cost telescopes: choose $\Phi$ so that $\hat{c}_i$ is small even when $c_i$ is large (the potential drops to absorb the spike).

Dynamic Array via Potential

Define $\Phi(D) = 2 \cdot \text{size}(D) - \text{capacity}(D)$.

After initialization: $\Phi = 2 \cdot 0 - 1 = -1$. But we want $\Phi \geq 0$; adjust to $\Phi = 2(\text{size} - \text{capacity}/2)$, which is $0$ right after a resize and grows to $\text{capacity}$ when the array is full.

Ordinary push (no resize): $c_i = 1$, size increases by 1, capacity unchanged, $\Delta\Phi = 2$.

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

Resize push: array is full (size $= k = $ capacity), doubles to $2k$. $c_i = k + 1$ (copy $k$ elements plus the push). After resize: size $= k+1$, capacity $= 2k$, so $\Phi$ drops from $k$ to $2(k+1) - 2k = 2$. $\Delta\Phi = 2 - k$.

$$\hat{c}_i = (k+1) + (2 - k) = 3 = O(1)$$

In both cases, amortized cost is $O(1)$. The potential absorbs the spike during resize.

Splay Trees

A splay tree is a BST where every access (search, insert, delete) splays the accessed node to the root via a sequence of rotations. No balance information is stored; the tree self-organises by use.

The potential function is:

$$\Phi(T) = \sum_{x \in T} \log(\text{size}(x))$$

where $\text{size}(x)$ is the number of nodes in the subtree rooted at $x$. This is the sum of the ranks $r(x) = \log(\text{size}(x))$ over all nodes.

Access Lemma: the amortized cost of splaying a node $x$ to the root of a tree with root $t$ is at most $1 + 3(r(t) - r(x)) = O(\log n)$.

The proof analyzes each zig, zig-zig, and zig-zag rotation step and shows the potential drops enough to pay for the actual rotations. Over $m$ operations on a tree with $n$ nodes:

$$\sum_{i=1}^{m} c_i = O((m + n) \log n)$$

giving $O(\log n)$ amortized per operation. Splay trees achieve this without storing any balance information, and they adapt to access patterns - frequently accessed nodes migrate to the top.

Union-Find with Path Compression and Union by Rank

Union-Find (disjoint set union) supports two operations:

  • Find(x): return the root of $x$’s component.
  • Union(x, y): merge the components of $x$ and $y$.

Path compression: during Find, redirect all nodes on the path to point directly to the root. Union by rank: always attach the shorter tree under the taller one.

With both optimisations, the amortized cost per operation is $O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function - a function that grows so slowly it is effectively constant for all practical $n$ (it is $\leq 4$ for $n \leq 2^{2^{2^{2^{16}}}}$, a number far larger than atoms in the observable universe).

The formal proof uses a potential function that accounts for the structure of the trees and the distribution of node ranks. The key insight is that path compression drastically reduces future Find costs, and union by rank keeps trees shallow enough that the amortized cost stays nearly constant.

Examples

Example 1 - Stack with MultiPop: A stack supports Push (cost 1), Pop (cost 1), and MultiPop($k$) (pop $k$ elements, cost $\min(k, \text{stack size})$). Over $n$ operations, the total cost is $O(n)$: every element can be pushed at most once and popped at most once, regardless of how many MultiPop calls occur. Amortized cost: $O(1)$ per operation.

Example 2 - Amortized $O(1)$ for splay vs. $O(\log n)$ for AVL: For a sequence of $m$ accesses to the same element in a splay tree, the total cost is $O(m + \log n)$ - the element reaches the root after the first access and stays there. An AVL or Red-Black tree always pays $O(\log n)$ per access with no adaptation to access patterns.

Example 3 - Hash table rehashing: A hash table doubles its capacity when load factor exceeds $0.75$. Using the potential $\Phi = 2 \cdot \text{size} - \text{capacity}$, every insert costs $O(1)$ amortized. The same analysis applies whether chaining or open addressing is used.

Summary of Amortized Techniques

Technique Mechanism Best for
Aggregate Total cost divided by $n$ Simple counting arguments
Accounting Assign credits to operations Showing “future work is pre-paid”
Potential $\hat{c}_i = c_i + \Delta\Phi$ Complex structures; formal proofs

The choice of technique is a matter of what makes the proof clearest. The potential method is most general: once you find the right $\Phi$, the algebra is mechanical. Finding the right $\Phi$ is the art.

Read Next: