Amortized Analysis and Cost Distribution¶

Some operations are expensive occasionally but cheap on average; spreading cost across many operations enables structures that appear to violate worst-case bounds (dynamic arrays, splay trees).

Tension Addressed¶

Access Speed vs. Modification Speed

Recognizable As¶

Dynamic array doubling strategy; hash table resize; splay tree restructuring; any "occasional expensive operation" pattern with good average performance

Canonical Sources¶

Tarjan, "Amortized Computational Complexity" (1985); CLRS, Introduction to Algorithms, Chapter 17 (1990)

Transfers To¶

Capacity Planning (burst handling), Garbage Collection (incremental vs. stop-the-world), Financial Systems (amortized depreciation)

The "pay it forward" or "banking" mental model helps reason about amortized structures.