Amortized Analysis
/ˈæm.ər.taɪzd əˈnæl.ɪ.sɪs/ · Noun · Development · Origin: 1985
Definitions
Amortized Analysis is a technique in algorithm analysis that determines the average performance of each operation over a worst-case sequence of operations, providing a more accurate picture of an algorithm's cost than worst-case analysis of individual operations. The key insight is that expensive operations may be infrequent enough that their cost, spread across all operations, is much lower than the worst case suggests. The classic example is a dynamic array (like Python's list or Java's ArrayList): appending an element is O(1) most of the time, but occasionally triggers an O(n) resize operation that copies all elements to a larger array. Amortized analysis shows that the average cost per append is still O(1) because the expensive resize happens exponentially less often as the array grows. Three main techniques exist: the aggregate method (total cost divided by number of operations), the accounting method (assigning amortized costs and maintaining a credit balance), and the potential method (using a potential function to track stored energy). Amortized analysis is essential for understanding data structures like splay trees, hash tables with resizing, and union-find.
In plain English: Looking at the average cost of an operation over many uses instead of the worst single case. It's why dynamic arrays are still fast even though they occasionally need to resize.
Example: "ArrayList.add() is O(1) amortized — yes, it occasionally does an O(n) resize, but that happens so rarely the average stays constant."
Origin Story
The accounting trick that makes occasionally slow operations look fast
**Amortized analysis** was formalized by Robert Tarjan in his 1985 paper 'Amortized Computational Complexity.' The insight: some operations are expensive occasionally but cheap most of the time. Averaging the cost over a sequence of operations gives a more useful performance guarantee.
The classic example is a dynamic array (like Python's `list` or Java's `ArrayList`). Appending is O(1) most of the time, but occasionally triggers an O(n) resize. Amortized analysis shows the average cost per append is still O(1) because resizes double the capacity, making them exponentially rare.
Tarjan introduced three methods: the aggregate method (total cost divided by operations), the accounting method (overcharge cheap operations to 'save up' for expensive ones), and the potential method (using a potential function like physics). All three give the same answers.
Coined by: Robert Tarjan
Context: 'Amortized Computational Complexity,' 1985
Fun fact: Tarjan is one of the most prolific algorithm designers in history -- he co-invented splay trees, Fibonacci heaps, and the union-find data structure. He won the Turing Award in 1986 at age 38, partly for his work on amortized analysis.