= Amortized analysis
{title2=$\widehat c_i=c_i+\Phi_i-\Phi_{i-1}$}
<Amortized analysis> bounds the total cost of every permitted <sequence> of operations from a specified initial state. An amortized $O(1)$ bound means that some constants $a,b$ satisfy $\sum_{i=1}^m c_i\leq am+b$ for every such <sequence> of length $m$. 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 https://epubs.siam.org/doi/10.1137/0606031[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.
Back to article page
