 Amortized analysis

Bounds the total cost of a sequence of operations, rather than a probability-weighted average. If a nonnegative potential $\Phi$ assigns stored credit to states, define ${\hat{c}}_i=c_i+{\Phi }_i-{\Phi }_{i-1}$. Then $\sum c_i=\sum {\hat{c}}_i+{\Phi }_0-{\Phi }_m$. Starting with zero potential, constant amortized costs imply linear total cost.

// Destination: computer-science.bigb