Amortized Time

An average time for performing an operation.

$\text{Amortized time}=\frac{\text{operations or time for num. elements}}{\text{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 $\frac{t(n)}{n}$. If we plot this on a graph using $n$ as the $x$-coordinate and $\frac{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: $\frac{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)$