Amortized Time

An average time for performing an operation.

${\mbox{Amortized time}}={\frac {\mbox{operations or time for num. elements}}{\mbox{num. elements}}}$

Plotting

Suppose that $t(n)$ is the time recorded for an input size of $n$ elements. The amortized cost per operation would be ${\tfrac {t(n)}{n}}$. If we plot this on a graph using $n$ as the $x$-coordinate and ${\tfrac {t(n)}{n}}$ as the $y$-coordinate, we can see how time relates to input size.

Amortized time can also be considered a way to determine the coefficients for a known behavior. For example, if we know that a function runs in $O(n\log {n})$ time, we can estimate the coefficient with the following fraction: ${\tfrac {t(n)}{n\log {n}}}$.

Common Plot Types

See Asymptotic Analysis for information on Big-O notation.

• Constant: $O(1)$
• Linear: $O(n)$
• Logarithmic: $O(\log {n})$
• Quadratic: $O(n^{2})$
• Exponential: $O(k^{n})$