Amortized analysis

Summary

Amortized analysis bounds the total cost of a sequence of operations on a data structure, rather than the cost of each operation alone. An occasional expensive operation is paid for by many cheap ones. So the worst-case average cost per operation over a sequence can be much smaller than the worst single cost. The main techniques are the aggregate method, the accounting method and the potential method.