Amortized Analysis: Why It's Fast Even When It Looks Slow

Quick Revisit

• USE WHEN: inner loop looks O(n) but a global bound limits total work (two pointers, stack pops, DSU)
• INVARIANT: total work across all n operations ≤ cn, even if a single operation costs O(n)
• TIME: O(n) amortized total for n operations | SPACE: varies
• CLASSIC BUG: claiming amortized O(1) without a valid argument — nested loops aren't always amortized
• PRACTICE: 08-ladder-mixed

Your teammate says "this loop runs $O(n)$ inside another $O(n)$ loop, so it's $O(n^2)$." You smile and say "actually, it's $O(n)$ total." This is amortized analysis.

Difficulty: [Advanced]CF Rating Range: 1600-2200 Prerequisites: Basic complexity analysis, familiarity with data structures from Chapters 2-3

Contents

• Why Amortized Analysis Matters in CP
• Method 1: Aggregate (Just Count Everything)
• Method 2: Banker's (Credits)
• Method 3: Physicist's (Potential Function)
• Five CP Examples
• How to Recognize Amortized O(n)
• Practice Problems

---

Why Amortized Analysis Matters in CP

Worst-case analysis per operation sometimes lies. A single operation might take $O(n)$, but if that expensive operation only happens rarely, the average cost per operation (over $n$ operations) is $O(1)$. That's not average-case analysis (which assumes random inputs). It's amortized analysis: a worst-case bound on the total cost of a sequence of operations.

In CP, this matters because many correct solutions look $O(n^2)$ at first glance but are actually $O(n)$ or $O(n\log n)$ amortized. If you can't see the amortization, you might reject a correct approach or waste time optimizing something that's already fast enough.

Method 1: Aggregate (Just Count Everything)

The simplest method. Instead of analyzing one operation, count the total work across all operations and divide.

Example -- Two pointers:

int j = 0;
for (int i = 0; i < n; i++) {
    while (j < n && a[j] - a[i] <= k) j++;
    // process window [i, j)
}

The inner while looks like it runs up to $O(n)$ per iteration of the outer for, suggesting $O(n^2)$. But j only moves forward. Across all iterations of the outer loop, j increments at most $n$ times total. The total work of the inner loop is $O(n)$, not $O(n)$ per iteration.

Total: $O(n)$ for the entire double loop.

Method 2: Banker's (Credits)

Each cheap operation deposits "credits" (pre-paid work). When an expensive operation occurs, it spends the saved credits.

Example -- Dynamic array (vector push_back with doubling):

When the array is full (capacity $c$), push_back allocates $2c$ space and copies all $c$ elements. That's $O(c)$ work for one operation. Looks terrible.

Credit scheme: Each push_back pays 3 coins:

• 1 coin for the actual insertion.
• 2 coins saved for later (one for copying itself, one for copying an element that was already present when this element was added).

When doubling occurs at capacity $c$, there are $c/2$ new elements (added since the last doubling), each having saved 2 coins -> $c$ coins available. Copying $c$ elements costs exactly $c$ coins. The account never goes negative.

Amortized cost per push_back: $O(1)$.

Method 3: Physicist's (Potential Function)

Define a potential function $\mathrm{\Phi }(\text{state})$ that measures "stored-up work." The amortized cost of an operation is:

$${\hat{c}}_i=c_i+\mathrm{\Phi }(\text{after})-\mathrm{\Phi }(\text{before})$$

If $\mathrm{\Phi }$ starts at 0 and is always $\ge 0$, then $\sum {\hat{c}}_i\ge \sum c_i$, so the amortized costs are a valid upper bound on the actual total cost.

Example — small-to-large merging:

Let $\mathrm{\Phi }$ = $\sum _v{\log }_2|S_v|$ over all live containers. Every time an element moves from a smaller container to a larger one, the receiving container's size at least doubles, so its contribution to $\mathrm{\Phi }$ increases by at least 1 — but the source side decreases too. A clean accounting gives amortized $O(\log n)$ per element across the whole run, matching the total $O(n\log n)$. The same potential lens works for DSU union-by-size.

(Splay trees and link-cut trees are the classic textbook potential-function examples. They are legitimate but rarely on the contest path; if you need them, see CLRS or Tarjan's Data Structures and Network Algorithms.)

Five CP Examples

1. Two Pointers -- $O(n)$ Despite Nested Loops

As shown above: both pointers traverse the array at most once each. Total pointer movement: $O(n)$. The inner loop is not $O(n)$ per outer iteration -- it's $O(n)$ total across all outer iterations.

2. DSU with Path Compression -- Inverse Ackermann

Each find operation flattens a path, making future find operations faster. A single find can traverse $O(n)$ nodes, but after it runs, those nodes point directly to the root. The aggregate method over $m$ operations on $n$ elements gives $O(m\cdot \alpha (n))$ total, where $\alpha$ is the inverse Ackermann function -- effectively $O(1)$ per operation.

3. Monotonic Stack -- Each Element Pushed and Popped Once

stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] >= a[i])
        st.pop();  // looks O(n) per iteration
    st.push(i);
}

Each of the $n$ elements is pushed exactly once and popped at most once. Total push + pop operations: $\le 2n$. The inner while loop is $O(n)$ total, not $O(n)$ per iteration. Amortized $O(1)$ per element.

4. Heavy Path Decomposition Queries -- $O({\log }^{2}n)$ per Query

A path from $u$ to $v$ crosses at most $O(\log n)$ heavy chains (because each light edge at least doubles the subtree size -- the same doubling argument as small-to-large merging). Each chain query takes $O(\log n)$ via segment tree. Total: $O({\log }^{2}n)$ per path query.

The amortization here is structural: the tree decomposition guarantees few chain transitions. It's the aggregate method applied to the tree structure rather than to a sequence of operations.

5. Euler Tour Construction -- $O(n)$ Preprocessing for $O(1)$ LCA

Building the Euler tour visits each edge twice: once going down, once going up. For a tree with $n$ nodes and $n-1$ edges, the tour has length $2n-1$. Despite the DFS recursion touching nodes multiple times, the total work is $O(n)$. Combined with sparse table on the Euler tour, this yields $O(1)$ LCA queries after $O(n\log n)$ preprocessing (or $O(n)$ with the Bender-Farach-Colton method using block decomposition).

How to Recognize Amortized $O(n)$

When you see nested loops or expensive operations inside loops, ask:

"Is there a quantity that changes monotonically across the entire execution?"

• Two pointers: Each pointer only moves forward -> $O(n)$ total movement.
• Monotonic stack: Each element enters and exits at most once -> $O(n)$ total.
• Queue-based BFS: Each node is enqueued and dequeued once -> $O(n)$ total.
• DSU path compression: Path length shrinks after each find -> amortized $O(\alpha (n))$.

The general pattern: each element is processed at most $O(1)$ times across all iterations, even if any single iteration could process many elements.

If every element can be "charged" to a unique event that happens $O(1)$ times, the total is $O(n)$.

When the amortized argument breaks

Three warning patterns. If any apply, double-check (or abandon) the amortized claim.

• A pointer can move backward. Two pointers depend on monotone movement. If j ever decreases — say, the inner condition allows j-- — then j can traverse the array Θ(n) times, and the inner loop is genuinely $O(n^2)$. Same trap with stacks: if you push the same element twice through different code paths, the "each element popped once" argument fails.
• Items can be reinserted without growth. Small-to-large works because each move at least doubles the receiving container. If a problem allows inserting into a smaller container, or re-adding an element that was just removed, the doubling argument no longer applies. DSU has the same caveat: union without size/rank tracking can produce $O(n)$ chains.
• Cleanup repeats over the same large set. Patterns like "after each query, walk the whole window and reset state" look amortized but aren't — every query pays for the whole window. The fix is usually local rollback (only undo what this query touched) or a true potential argument showing the cleanup cost is paid by prior insertions.

The diagnostic: count the total work done by the suspicious inner loop across all outer iterations. If you cannot bound that count by something linear (or near-linear) in the input size, the amortized claim is wrong.

Practice Problems

Problem	Amortized Insight	CF Rating
CF 1944C - MEX Game 1	Greedy with amortized counting	1300
CF 1407D - Discrete Centroid	Reroot with amortized transitions	1800
CF 1619E - MEX and Increments	Maintain stack of costs, amortized pushes/pops	1700
CF 1476D - Journey	DP with "looks O(n²)" but O(n) total transitions	1700
CF 1614D1 - Divan and Kostomuksha (easy)	DP over divisors, harmonic sum amortization	1700
CF 1799D2 - Hot Start Up (hard)	DP with amortized state transitions	2100

Related Techniques

• Small-to-Large Merging -- the classic example of amortized O(n log n) from repeated merging
• Monotonic Stack -- each element is pushed and popped at most once, giving amortized O(n)
• Union-Find (DSU) -- path compression + union by rank gives amortized near-O(1) per operation

---