> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/data_structures/amortized_analysis.md).

# Amortized analysis

## Basic idea

Amortized analysis bounds the total cost of a worst-case operation sequence without assuming a probability distribution. Expensive individual operations are paid for by many cheap operations or by stored potential.

## Key formulas

* Aggregate method: show $\sum\_{i=1}^{n}c\_i\le T(n)$, giving amortized cost $T(n)/n$.
* Accounting method assigns credits so accumulated credit pays future actual cost.
* Potential method: $\hat c\_i=c\_i+\Phi(D\_i)-\Phi(D\_{i-1})$ with $\Phi(D\_i)\ge0$.
* Telescoping gives $\sum\_i c\_i\le\sum\_i\hat c\_i+\Phi(D\_0)$.
* Dynamic-array append is $O(1)$ amortized despite occasional $O(n)$ resizing.
* Path compression with union by rank gives disjoint-set operations an $O(\alpha(n))$ amortized bound.

## Resources

<https://en.wikipedia.org/wiki/Amortized_analysis>