Amortized analysis measures the cost of an operation by averaging it over a sequence of operations, rather than looking at the single worst case in isolation. In his 1985 paper “Amortized Computational Complexity,” Robert Tarjan adapts the financial sense of “amortize,” to put money aside at intervals for gradual payment of a debt, to mean “to average the running times of operations in a sequence over the sequence.”
The motivation is that a pure worst-case analysis can be unduly pessimistic when expensive operations are rare and are made possible only by many earlier cheap ones. Tarjan’s paper gives a simple example: a stack manipulated by a sequence of push and pop operations. A single sequence step might pop many items at once and so look costly, but over the whole sequence there can be at most as many pops as there were pushes, so the total work is bounded and the average per operation is small.
A familiar everyday case is the dynamic array, which doubles its underlying storage when it fills up. Any single insertion that triggers a resize is expensive because it copies every element, but those costly resizes are spread across many cheap insertions, giving an amortized cost of O(1) per insertion. The same reasoning explains the efficiency of self-adjusting structures such as splay trees.
Tarjan’s paper frames amortized running time as a measure that is “realistic but robust,” and argues that designing algorithms for low amortized cost yields data structures that are simpler and more flexible than their worst-case-optimized counterparts. The technique is now standard, often carried out with a “potential function” that tracks stored-up work the way a bank balance tracks prepaid debt.