47.04.01 · theoretical-cs / algorithms-analysis

Amortized Analysis: Aggregate, Accounting, and Potential-Function Methods

shipped3 tiersLean: none

Anchor (Master): CLRS 2022 Introduction to Algorithms 4e (MIT Press) §17.1-17.4; Tarjan 1985 Amortized Computational Complexity (SIAM J. Computing) (the potential-function framework, application to splay trees and union-find)

Intuition Beginner

Think about a notebook that holds 10 pages. You write entries one by one. Most of the time, you just write on the next blank page. But when the notebook fills up, you need to buy a new notebook with twice as many pages and copy all your old entries over. That copy takes a lot of time — much more than a single write.

Does this mean writing an entry is slow? Not really. The copy happens only once in a while. If you wrote 100 entries, the copy happened maybe once or twice. Averaged over all 100 writes, each one cost about as much as a single write plus a small fraction of the copy.

This is amortized analysis. Instead of asking "how much does the worst single operation cost?" it asks "how much do $n$ operations cost in total, per operation on average?" The worst-case cost of a single operation might be large (the notebook copy), but the amortized cost over a sequence is small.

There are three ways to compute the amortized cost. The aggregate method simply totals the work and divides. The accounting method (or token method) assigns a fixed charge to each operation, saves the surplus from cheap operations as credits, and spends credits on expensive ones. The potential method generalises the accounting method by defining a potential energy stored in the data structure that is released when expensive operations happen.

Visual Beginner

A dynamic array growing by doubling:

Insert into array of capacity 4 (size 3):
[1][2][3][ ]  →  [1][2][3][4]  ← cheap: O(1)

Insert into array of capacity 4 (size 4, full):
[1][2][3][4]  →  [1][2][3][4][5][ ][ ][ ]  ← expensive: allocate + copy
                new capacity 8

Insert into array of capacity 8 (size 5-7):
[1][2][3][4][5][6][ ]  ← cheap: O(1) each

Insert into array of capacity 8 (size 8, full):
→ allocate 16, copy 8 items  ← expensive again

Operation	Actual cost	Credits saved	Credits spent	Amortized cost
Insert (not full)	1	+2	0	3
Insert (triggers resize)	$n + 1$	0	$- n$	3
Insert (not full)	1	+2	0	3

The accounting method charges 3 tokens per insert. Cheap inserts bank 2 tokens. The resize spends the banked tokens on copying.

Worked example Beginner

A dynamic array starts with capacity 1 and doubles when full. Each insert into a non-full slot costs 1 (write the element). Each insert that triggers a resize costs $n + 1$ (copy $n$ old elements, write the new one, where $n$ is the current size before doubling).

Let us total the cost of $n$ insertions starting from an empty array. The resizes happen at sizes 1, 2, 4, 8, ..., up to the largest power of 2 below $n$ . The total copy cost is $1 + 2 + 4 + \dots + n /2 + n < 2 n$ (a geometric series). The $n$ writes each cost 1. So the total cost is at most $3 n$ .

The amortized cost per insertion is $3 n / n = 3$ . Each insert costs $O (1)$ amortized, even though individual inserts can cost $O (n)$ .

Check your understanding Beginner

Formal definition Intermediate+

Let a data structure undergo a sequence of $n$ operations with actual costs $c_{1}, c_{2}, \dots, c_{n}$ . The total actual cost is $T = \sum_{i = 1}^{n} c_{i}$ .

Aggregate method. Compute $T$ directly and report the amortized cost as $T / n$ .

Accounting method. Assign an amortized cost $\overset{c}{^}_{i}$ to each operation $i$ . Require that the credit balance never goes negative: for all $k$ , $\sum_{i = 1}^{k} \overset{c}{^}_{i} \geq \sum_{i = 1}^{k} c_{i}$ . Then $\sum_{i = 1}^{n} \overset{c}{^}_{i} \geq T$ , so the amortized costs upper-bound the actual total cost.

Potential method. Let $Φ$ be a potential function mapping the state $D_{i}$ of the data structure after operation $i$ to a non-negative real number, with $Φ (D_{0}) = 0$ for the initial state. The amortized cost of operation $i$ is:

\overset{c}{^}_{i} = c_{i} + Φ (D_{i}) - Φ (D_{i - 1}) .

The total amortized cost is:

i = 1 \sum n \overset{c}{^}_{i} = i = 1 \sum n c_{i} + Φ (D_{n}) - Φ (D_{0}) \geq i = 1 \sum n c_{i},

since $Φ (D_{n}) \geq 0$ and $Φ (D_{0}) = 0$ .

Counterexamples to common slips

"Amortized $O (1)$ means every operation is $O (1)$ ." No. Individual operations can be expensive ( $O (n)$ ). The amortized bound says the average over a sequence is $O (1)$ , not that each operation is.
"The accounting method and potential method are different analyses." The accounting method is a special case of the potential method where the potential equals the total credit balance. The potential method is more flexible because $Φ$ can be any function of the data structure state.
"Amortized analysis works for worst-case inputs." It does: the bound holds for any sequence of $n$ operations, not just for average-case or random inputs. The averaging is over operations in the sequence, not over probability distributions.

Key theorem with proof Intermediate+

Theorem (dynamic table: $O (1)$ amortized insertion). Consider a dynamic table that doubles its capacity when full. Starting from an empty table with capacity 1, the amortized cost of each insertion is $O (1)$ .

Proof (potential method). Define $Φ (D_{i}) = 2 \cdot size (D_{i}) - capacity (D_{i})$ , where $size$ is the number of elements and $capacity$ is the allocated array size. Note $Φ \geq 0$ always (size never exceeds capacity) and $Φ (D_{0}) = 0$ .

Case 1: Insertion without resize (size $<$ capacity before insertion). Actual cost $c_{i} = 1$ . After insertion, size increases by 1:

\overset{c}{^}_{i} = 1 + 2 (size + 1) - cap - (2 \cdot size - cap) = 1 + 2 = 3.

Case 2: Insertion with resize (size $=$ capacity $= k$ before insertion). Actual cost $c_{i} = k + 1$ (copy $k$ elements, write new element, capacity becomes $2 k$ ). After insertion, new size is $k + 1$ , new capacity is $2 k$ :

\overset{c}{^}_{i} = (k + 1) + 2 (k + 1) - 2 k - (2 k - k) = k + 1 + 2 - k = 3.

In both cases $\overset{c}{^}_{i} \leq 3 = O (1)$ . $□$

Bridge. The potential method is the foundational reason amortized analysis works as a rigorous tool: the potential $Φ$ captures the "stored work" in the data structure, and the amortized cost formula $\overset{c}{^}_{i} = c_{i} + ΔΦ$ ensures that total amortized cost upper-bounds total actual cost. This builds toward the analysis of red-black trees in 47.04.02, where rotations during rebalancing have $O (1)$ amortized cost, and it appears again in 47.04.03 where augmenting paths in network flow are charged against a potential that decreases with each augmentation. The central insight is that expensive operations consume potential built up by cheap ones, so the potential function serves as a "prepayment" scheme, and putting these together gives tight bounds on data structure performance that worst-case analysis alone cannot achieve.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib has no amortized analysis framework. Data structures in Mathlib (lists, arrays) are analysed by worst-case cost, and the potential-function method, accounting method, and aggregate method are absent as formal objects. A Codex.Algorithms.Amortized module with the potential method framework and a proof that dynamic table insertion has $O (1)$ amortized cost would be the foundational target; this unit ships without it.

Advanced results Master

The potential method is the most powerful and general framework for amortized analysis. Two advanced applications demonstrate its range.

Theorem 1 (splay tree amortized analysis). Every operation on a splay tree (access, insert, delete, join, split) takes $O (lo g n)$ amortized time, where $n$ is the number of nodes ^{[Tarjan 1985]}. The potential function is $Φ = \sum_{x \in T} lo g_{2} s (x)$ , where $s (x)$ is the size of the subtree rooted at $x$ . The access lemma shows that splaying a node $x$ to the root changes the potential by at most $3 (lo g_{2} s_{new} (x) - lo g_{2} s_{old} (x)) + 1 = O (lo g n)$ , which bounds the amortized cost. The static optimality theorem shows that splay trees perform within a constant factor of the optimal static binary search tree for any access sequence.

Theorem 2 (union-find with path compression). The union-find data structure with union by rank and path compression has amortized cost $O (α (n))$ per operation, where $α$ is the inverse Ackermann function ^{[Tarjan 1985]}. The analysis uses a potential function based on the "level" and "index" of each node in the union-find forest. The amortized cost of a find operation is $O (α (n))$ because each step along the find path either decreases the potential (a "good" step) or is one of at most $α (n)$ "bad" steps per node. Since $α (n) \leq 4$ for all practical $n$ , the amortized cost is effectively constant.

Synthesis. The potential method is the foundational reason amortized analysis extends beyond simple averaging to give tight bounds on sophisticated data structures: the potential $Φ$ encodes the structural state of the data structure as a numerical quantity, and the amortized cost formula $\overset{c}{^} = c + ΔΦ$ turns the analysis into an accounting exercise. The central insight is that the potential serves as a "savings account" built during cheap operations and spent during expensive ones, and putting these together with the right potential function for each data structure (subtree sizes for splay trees, levels for union-find, load factor for dynamic tables) yields tight $O (1)$ or $O (lo g n)$ amortized bounds. This builds toward the analysis of network flow in 47.04.03 where augmenting paths are charged against a distance potential, and it appears again in 47.04.02 where red-black tree rebalancing is $O (1)$ amortized per update.

Full proof set Master

Proposition 1 (dynamic table doubling: $O (1)$ amortized). $n$ insertions into a dynamic table that doubles when full cost $O (n)$ total.

Proof. The table doubles at sizes $1, 2, 4, \dots, 2^{k}$ where $2^{k}$ is the smallest power of 2 at least $n$ . The copy costs are $1 + 2 + 4 + \dots + 2^{k - 1} = 2^{k} - 1 < 2 n$ . The $n$ insertions each cost 1 to write. Total: $n + 2 n - 1 = O (n)$ . $□$

Proposition 2 (binary counter: $O (1)$ amortized per increment). $n$ increments of a binary counter starting from 0 flip $O (n)$ bits total.

Proof. Use $Φ =$ number of 1-bits. Each increment flips $t + 1$ bits (where $t$ is the number of trailing 1s). The potential decreases by $t - 1$ : $t$ ones become zeros and one zero becomes a one. Amortized cost: $(t + 1) + (1 - t) = 2$ . Total: $2 n$ . $□$

Proposition 3 (multipop stack: $O (1)$ amortized). A stack supporting PUSH, POP, and MULTIPOP( $k$ ) has $O (1)$ amortized cost per operation using the potential $Φ = s$ (stack size).

Proof. PUSH: actual cost 1, $ΔΦ = 1$ , amortized $= 2$ . POP: actual cost 1, $ΔΦ = - 1$ , amortized $= 0$ . MULTIPOP( $k$ ): actual cost $min (k, s)$ , $ΔΦ = - min (k, s)$ , amortized $= 0$ . Since $Φ \geq 0$ and $Φ (D_{0}) = 0$ , total amortized cost $\geq$ total actual cost. Total amortized for $n$ operations: at most $2 n$ . $□$

Connections Master

50.03.01 — Big-O notation and complexity analysis provide the language for expressing amortized bounds; the distinction between worst-case and amortized cost parallels the distinction between worst-case and average-case analysis.
01.01.01 — Fields and basic algebra underpin the arithmetic of potential functions; the requirement $Φ \geq 0$ and $Φ (D_{0}) = 0$ uses ordered field properties.
47.04.02 — Red-black tree rebalancing uses $O (1)$ amortized rotations per update; the potential method applies to the analysis of tree height invariants.
47.04.03 — Network flow algorithms use amortized arguments to bound the total work across all augmenting path iterations.

Historical & philosophical context Master

Amortized analysis was introduced by Robert Tarjan in his 1985 paper "Amortized Computational Complexity" ^{[Tarjan 1985]}. Tarjan developed the potential-function framework to analyse splay trees, which he had introduced with Daniel Sleator in 1983. The key insight was that splay trees, despite having no explicit balance condition, achieve $O (lo g n)$ amortized performance — a result invisible to worst-case analysis, since individual operations can trigger long chains of rotations.

The term "amortized" comes from finance, where an expense is spread over multiple periods. Tarjan's contribution was to make this intuition mathematically precise via the potential function, turning a financial metaphor into a proof technique. The accounting method was known informally before Tarjan's paper, but the potential method unified and generalised it, enabling the analysis of union-find, splay trees, and dynamic tables within a single framework.

Bibliography Master

@book{clrs2022,
  author    = {Cormen, T. H. and Leiserson, C. E. and Rivest, R. L. and Stein, C.},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@article{tarjan1985amortized,
  author  = {Tarjan, Robert Endre},
  title   = {Amortized Computational Complexity},
  journal = {SIAM Journal on Algebraic and Discrete Methods},
  volume  = {6},
  number  = {2},
  pages   = {306--318},
  year    = {1985},
}
@article{sleator1985self,
  author  = {Sleator, Daniel D. and Tarjan, Robert Endre},
  title   = {Self-Adjusting Binary Search Trees},
  journal = {Journal of the ACM},
  volume  = {32},
  number  = {3},
  pages   = {652--686},
  year    = {1985},
}

Prerequisites

50.03.01
01.01.01

Tier anchors

beginner: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §17.1 (why some operations are expensive only rarely, averaging over a sequence)
intermediate: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §17.1-17.3 (aggregate method, accounting (tokens), potential-function method, dynamic table example)
master: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §17.1-17.4; Tarjan 1985 Amortized Computational Complexity (SIAM J. Computing) (the potential-function framework, application to splay trees and union-find)

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Section 17.1 introduces amortized analysis as a technique for bounding the total cost of a sequence of operations rather than individual operations; the aggregate method computes $T (n) / n$ directly. Section 17.2 presents the accounting method where each operation is charged an amortized cost, with credits banked and spent to cover expensive future operations. Section 17.3 develops the potential method: for a data structure with states $D_{0}, D_{1}, \dots, D_{n}$ , a potential function $Φ : states \to R_{\geq 0}$ with $Φ (D_{0}) = 0$ gives amortized cost $\overset{c}{^}_{i} = c_{i} + Φ (D_{i}) - Φ (D_{i - 1})$ , and the total amortized cost $\sum \overset{c}{^}_{i} = \sum c_{i} + Φ (D_{n}) - Φ (D_{0}) \geq \sum c_{i}$ bounds the actual cost. Section 17.4 analyses dynamic tables with expansion factor 2: $n$ insertions cost $O (n)$ total, so $O (1)$ amortized per insertion.
Tarjan, R. E. — Amortized Computational Complexity · SIAM Journal on Computing 15(2) (1986). Develops the potential-function framework as a unifying technique for amortized analysis, with applications to splay trees (access, join, and split in $O (lo g n)$ amortized), the union-find data structure (inverse-Ackermann amortized bound), and dynamic tables. Tarjan observes that the potential method generalises the accounting method by allowing the "bank balance" to be any non-negative function of the data structure state.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m