Common Growth Classes
Why
We are regularly referring to a few common growth classes.
Definitions
Let $c \in \R $. Then we name the following growth classes
| growth class | name |
|---|---|
| $O(1)$ | constant growth class |
| $O(\log(x))$ | logarithmic growth class |
| $O(\log(x)^c)$ | polylogarithmic growth class |
| $O(x)$ | linear growth class |
| $O(x^2)$ | quadratic growth class |
| $O(x^c)$ | polynomial growth class |
| $O(c^x)$ | exponential growth class |
We have written these in order:
\[
O(1) \subset O(\log(x)) \subset O((\log(x))^c) \subset \cdots
\subset O(x^c) \subset O(c^x).
\]
A function that grows faster (is in the upper growth class) of a power of $x$ is called superpolynomial. One that grows slower than $c^n$ for some $c \in \R $ is called subexponential. The class $O(\log(x^c))) = O(\log(x))$ since $\log(x^c) = c\log x$. Similarly, for all $c_1, c_2 > 0$, $O(\log_{c_1}(x)) = O(\log_{c_2}(x))$.
This list is useful because of the following
Let $f, g: \R \to \R $ and defined $h: \R
\to \R $ by $h = f + g$. If $O(f) \subset
O(g)$, then $h \in O(g)$.
In other words, if a function $h$ is the sum
of $f$ and $g$ and $g$ is growing faster, then
$g$ (the one growing faster) determines the order
of $h$.