Amortized Analysis
Amortized analysis bounds the average cost per operation over a worst-case sequence of operations, showing that occasionally expensive operations can be cheap when their cost is spread across many cheap ones.
Definition
Amortized analysis is a method for bounding the total cost of a sequence of operations on a data structure and dividing by the number of operations, yielding an amortized cost per operation that holds in the worst case over the whole sequence even when individual operations differ widely in cost.
Scope
This topic covers the three standard techniques of amortized analysis — the aggregate method, the accounting (banker's) method, and the potential method — and their application to data structures whose individual operations vary in cost, such as dynamic arrays, binary counters, splay trees, and the disjoint-set (union-find) structure. It distinguishes amortized cost from average-case cost and worst-case-per-operation cost.
Core questions
- How does amortized cost differ from worst-case-per-operation and average-case cost?
- How does the aggregate method bound the total cost of an operation sequence?
- How does the accounting method assign credits to pay for later expensive operations?
- How does the potential method use a potential function to smooth out costs?
- Which data structures rely on amortized guarantees rather than per-operation bounds?
Key concepts
- amortized cost
- aggregate method
- accounting (banker's) method
- potential method
- potential function
- dynamic array doubling
- binary counter increment
- union-find with path compression
Key theories
- Potential method
- The potential method assigns a nonnegative potential to the data structure's state; the amortized cost of an operation is its actual cost plus the change in potential, so cheap operations build potential that pays for later expensive ones.
- Accounting (banker's) method
- The accounting method charges some operations more than their actual cost, storing the surplus as credit on data-structure elements to pay for future expensive operations, ensuring credit never goes negative.
Clinical relevance
Amortized analysis explains why many widely used structures are efficient in practice despite occasional costly operations: dynamic arrays (resizable lists), hash tables that rehash, union-find used in connectivity and minimum-spanning-tree algorithms, and self-adjusting structures like splay trees all rely on amortized rather than per-operation guarantees.
History
The term and the systematic framework for amortized analysis were introduced by Robert Tarjan in 1985, drawing on earlier ad hoc arguments. The technique was central to analyzing the self-adjusting data structures (splay trees, Fibonacci heaps) developed by Tarjan and Sleator in the 1980s.
Key figures
- Robert Tarjan
- Daniel Sleator
Related topics
Seminal works
- tarjan1985amortized
- cormen2009
Frequently asked questions
- Is amortized cost the same as average-case cost?
- No. Average-case cost is an expectation over a probability distribution of inputs and can be violated by an unlucky input. Amortized cost is a worst-case guarantee over a sequence of operations with no randomness assumed: the total cost of any such sequence is bounded, so the average per operation always holds.
- Why is appending to a dynamic array O(1) amortized when resizing is O(n)?
- Because the array typically doubles its capacity, resizes are rare relative to appends, and the total copying work over a sequence of n appends is proportional to n. Spread across all appends, that gives a constant amortized cost even though a single resize is linear.