= Amortized time complexity
{title2=$T(m,n)\leq ma(n)+I(n)$}
An <amortized analysis> can bound the total <time complexity> $T(m,n)$ of every allowed <sequence> of $m$ operations by $ma(n)+I(n)$, where $n$ is a size parameter and $I(n)$ accounts for initialization or the specified initial state. The bound $a(n)$ is then an amortized per-operation <time complexity>. Dividing the total bound by $m$ explains the averaging; it is a guarantee over every permitted <sequence>, without an assumed <probability distribution> on requests. Individual operations can cost more than $a(n)$.
Back to article page
