zhuang@linux:~/reading/introduction-to-algorithms/03-characterizing-running-times/$ less
Characterizing Running Times
This post extracts some knowledge from Introduction to Algorithms Chapter 3 – Characterizing Running Times.
Asymptotic notation
Asymptotic notation describes how a running time grows as the input size $n$ becomes large. It ignores constant factors and lower-order terms, so we can focus on the main growth trend.
Big-O notation
$O(g(n))$ gives an asymptotic upper bound.
If $f(n) = O(g(n))$, then $f(n)$ grows no faster than $g(n)$, up to a constant factor.
Example: $3n^2 + 10n + 5 = O(n^2)$.
Omega notation
$\Omega(g(n))$ gives an asymptotic lower bound.
If $f(n) = \Omega(g(n))$, then $f(n)$ grows at least as fast as $g(n)$, up to a constant factor.
Example: $3n^2 + 10n + 5 = \Omega(n^2)$.
Theta notation
$\Theta(g(n))$ gives an asymptotic tight bound.
If $f(n) = \Theta(g(n))$, then $f(n)$ grows at the same rate as $g(n)$, up to constant factors.
Example: $3n^2 + 10n + 5 = \Theta(n^2)$.
Little-o notation
$o(g(n))$ gives an upper bound that is not tight.
If $f(n) = o(g(n))$, then $f(n)$ grows strictly slower than $g(n)$.
Example: $n = o(n^2)$.
Little-omega notation
$\omega(g(n))$ gives a lower bound that is not tight.
If $f(n) = \omega(g(n))$, then $f(n)$ grows strictly faster than $g(n)$.
Example: $n^2 = \omega(n)$.
Quick comparison
| Notation | Meaning | Intuition |
|---|---|---|
| $O(g(n))$ | upper bound | at most this fast |
| $\Omega(g(n))$ | lower bound | at least this fast |
| $\Theta(g(n))$ | tight bound | exactly this growth rate |
| $o(g(n))$ | strict upper bound | slower than this |
| $\omega(g(n))$ | strict lower bound | faster than this |
Common growth order
From slower to faster growth:
$$ 1 < \log n < n < n \log n < n^2 < n^3 < 2^n < n! $$
The running time with the slower growth rate is usually better for large inputs.
zhuang@linux:~/reading/introduction-to-algorithms/03-characterizing-running-times/$ comments