Amortized Analysis

The amortized cost per operation for a sequence of $n$ operations is the total cost of the operations divided by $n$.

Amortized cost, in Finance/Accounting, has a specific meaning. It generally means to gradually write off the initial cost of an asset over a period. In the Analysis of Algorithms, you can generally take it to mean as an average cost of an operation/algorithm (averaged over the number of times it is invoked; not to be confused with average case analysis which provides the expected runtime when the input is randomly drawn from a distribution assumed to be representative of the typical inputs to the algorithm.).

If we run an operation $n$ times where each run involves $1$ (RAM) step, followed by another run of the same operation that involves $n$ steps (due to some worst-case condition being met), the amortized cost of this operation is

$$ \frac{n + n}{n + 1} < \frac{2n}{n} = 2 \in O(1) $$

Note the worst-case analysis for the operation (example above) would yield $O(n)$ (which is too pessimistic) but amortized analysis gives $O(1)$ (more realistic).

The motivation for amortized analysis is that looking at the worst-case runtime per operation, rather than per algorithm, can be too pessimistic.

Amortized cost analysis is helpful because core operations of some data structures occasionally incur a large cost as they perform rebalancing or improvement of the data structures' internal state. Those expensive processes however, do not occur too frequently. Amortized analysis therefore yields an asymptotic bound closer to the true cost of using the data structure compared to a standard worst-case bound.

Resources