Amortized analysis bounds the total cost of every permitted sequence of operations from a specified initial state. An amortized bound means that some constants satisfy for every such sequence of length . The cost model and allowed operations are part of the claim; Big O notation alone does not specify them.
- A worst-case bound for one operation limits its cost in any reachable state. Summing these separate maxima can overestimate the cost of a whole sequence because expensive states may take many cheap operations to rebuild.
- An amortized analysis limits the total over every allowed sequence, including an unfavourably chosen one. Dividing that bound by the number of operations is a deterministic guarantee about the sequence.
- A probabilistic average-case analysis bounds an expected value under a stated probability distribution on inputs. For a randomized algorithm, an expected value can instead average over its random choices. Neither interpretation is required by a deterministic amortized analysis.
This distinction, and the credit and potential method viewpoints, are developed in R. Endre Tarjan's 1985 paper Amortized Computational Complexity, sections 1–2, pp. 306–308. The dynamic array doubling example below shows how an expensive operation can pay for itself through the cheap operations that precede it.
New to topics? Read the docs here!