Amortized Analysis

Bound the total cost of a sequence of operations, even when individual operations are expensive. An operation may cost $O(n)$ occasionally, yet the average over any sequence is $O(1)$.

The three methods

1. Aggregate

Bound the total cost of $m$ operations directly, then divide.

Example: a monotonic stack over $n$ elements. Each element is pushed once and popped at most once, so the total is $O(n)$ regardless of how long any single while loop runs.

2. Accounting (the banker’s method)

Charge each operation a fixed “fee”; cheap operations bank credit that expensive ones spend.

Example: vector::push_back. Charge 3 units per insertion — 1 to insert, 2 banked. When the array doubles, every element in the old half has 2 banked units, exactly paying for the copy.

3. Potential

Define $\Phi (\text{state})\ge 0$ with $\Phi (\text{initial})=0$. The amortized cost is

${\hat{c}}_i=c_i+{\Phi }_i-{\Phi }_{i-1},$

and since $\Phi$ never goes negative, $\sum {\hat{c}}_i\ge \sum c_i$.

Example: segment tree beats, where $\Phi$ counts the distinct values across all nodes. Each expensive recursion merges two values, decreasing $\Phi$.

Where it appears

Structure / algorithm	Amortized bound	Argument
vector::push_back	$O(1)$	doubling; accounting
DSU	$O(\alpha (n))$	path compression + union by size
Monotonic stack/queue	$O(1)$	each element pushed and popped once
Two pointers	$O(1)$	pointers only move forward
Prefix function, Z-function	$O(1)$	the pointer never decreases below its total increase
Kasai	$O(1)$	$k$ decreases at most $n$ times
Splay tree / link-cut tree	$O(\log n)$	potential = sum of $\log$ subtree sizes
Segment tree beats	$O({\log }^{2}n)$	potential = distinct values
Hash table with rehashing	$O(1)$	doubling
Ukkonen’s algorithm	$O(1)$ per character	the active length is bounded
Fibonacci heap decrease-key	$O(1)$	potential = trees + marked nodes
”Next free slot” DSU	$O(\alpha )$	each slot is consumed once
Small-to-large merging	$O(\log n)$ per element	each element moves $O(\log n)$ times

The two workhorse arguments

”Each element is touched $O(1)$ times”

The monotonic stack, two pointers, and the prefix function all rest on this. The inner while loop can run long, but every iteration removes something that can only be added once.

for (int i = 0; i < n; i++) {
    while (!st.empty() && cond(st.top(), a[i])) st.pop();   // total pops <= total pushes = n
    st.push(a[i]);
}

”Each element moves $O(\log n)$ times”

Small-to-large merging: when merging two sets, always move the smaller into the larger. An element’s set at least doubles each time it moves, so it moves at most $\log n$ times. Total $O(n\log n)$.

This one argument justifies DSU on tree, merging sets in tree DP, and union by size.

Amortized vs worst case — when it matters

Setting	Amortized acceptable?
Total time limit (all contests)	yes
Real-time systems	no — a single slow operation may miss a deadline
Interactive problems with per-query limits	usually yes
Persistent structures	amortized bounds often break under persistence

The last row is a genuine subtlety: amortized analysis assumes a single timeline. If an old version can be re-used repeatedly (as in persistence), the banked credit is spent many times and the bound fails. Splay trees, for instance, do not remain $O(\log n)$ amortized when made persistent.

Proving your own bound

1. Identify what makes an operation expensive.
2. Find a quantity that the expensive operation reduces.
3. Bound how much that quantity can increase per cheap operation.
4. Since it starts bounded and never goes negative, the total expensive work is bounded.

That is the potential method, and it is usually the easiest of the three to apply to a new structure.

See also: Monotonic Stack · DSU · Complexity Theory