Amortized Time Complexity

Definition

Amortized time complexity is the average time cost per operation over a worst-case sequence of operations, used to describe algorithms where occasional expensive operations are offset by many cheap ones.

Overview

Ordinary worst-case time complexity analyzes a single operation in isolation and assumes the worst possible input every time it's called. That analysis can be misleadingly pessimistic for data structures where an expensive operation only happens rarely and effectively pays for a string of cheap operations that follow it. Amortized analysis instead looks at a sequence of operations as a whole and asks: what is the average cost per operation across the worst possible sequence, not the worst possible single call? The canonical example is a dynamic array (such as Python's list or Java's ArrayList) that doubles its capacity when it fills up. Appending an element is usually O(1), but occasionally the array is full and appending triggers an O(n) resize and copy. Analyzed operation by operation, that resize looks like it makes appends O(n) in the worst case. But because doubling means resizes become exponentially rarer as the array grows, the total cost of all the resizes across n appends is bounded by O(n), which spread evenly gives an amortized cost of O(1) per append — matching how the structure actually behaves in practice. Three standard techniques are used to prove amortized bounds formally: the aggregate method, which sums total cost over n operations and divides by n; the accounting method, which assigns each operation a fixed "charge" and lets cheap operations bank credit that expensive ones later spend; and the potential method, which defines a potential function over the data structure's state and tracks how it rises and falls with each operation. Amortized analysis appears throughout common data structures beyond dynamic arrays, including the union-find (disjoint-set) structure with path compression and union by rank, splay trees, and hash tables with incremental resizing, and it's a frequent topic in technical interviews because it separates candidates who understand asymptotic behavior from those who only match memorized big-O labels to data structure names.

Key Concepts

• Analyzes average cost per operation over a full sequence, not a single call
• Distinguishes from worst-case analysis, which can overstate typical cost
• Classic example: dynamic array doubling giving amortized O(1) append
• Proven via the aggregate method, accounting method, or potential method
• Applies to union-find, splay trees, and incrementally resized hash tables
• Does not require probabilistic assumptions about input, unlike average-case analysis
• Bounds hold for any sequence of operations, including adversarial ones

Use Cases

Frequently Asked Questions

Related in Computer Science