Asymptotic notation

Definition

Let $f$ and $g$ be functions from the natural numbers to the non-negative real numbers.

• $f(n) = O(g(n))$ when there are constants $c > 0$ and $n_0$ with $f(n) \le c \cdot g(n)$ for each $n \ge n_0$. So $f$ grows at most as fast as $g$.
• $f(n) = \Omega(g(n))$ when there are constants $c > 0$ and $n_0$ with $f(n) \ge c \cdot g(n)$ for each $n \ge n_0$. So $f$ grows at least as fast as $g$.
• $f(n) = \Theta(g(n))$ when $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. So $f$ and $g$ grow at the same rate.
• $f(n) = o(g(n))$ when $f(n)/g(n) \to 0$, and $f(n) = \omega(g(n))$ when $f(n)/g(n) \to \infty$.

The sign $=$ here means "is in the set". $O(g)$ is a set of functions, and $f = O(g)$ means $f \in O(g)$.

Examples and non-examples

• $3n^2 + 10n + 7 = \Theta(n^2)$. Take $c = 4$ and $n_0 = 12$ for the upper bound, and $c = 3$ for the lower bound.
• $n \lg n = O(n^2)$, but $n \lg n \ne \Omega(n^2)$.
• $\lg(n!) = \Theta(n \log n)$. The base of a logarithm changes only a constant factor, so $O(\log n)$ needs no base.
• $2^{n+1} = O(2^n)$, but $2^{2n} \ne O(2^n)$.
• Not an example: $n^{\sin n}$ is not $O(1)$, and it is not $\Omega(n^{1/2})$ either. Some functions do not compare.

Related definitions

• Cost measures. The time of an algorithm is a function of the size of the input. A claim such as "the worst-case time is $\Theta(n \log n)$" uses the maximum over the inputs of size $n$. The comparison model is one way to fix what one step is.
• Amortized and expected costs use the same notation on an average over a sequence of operations, or over random choices.

References

1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, Chapter 3
2. Donald E. Knuth, Big Omicron and big Omega and big Theta (1976)