\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Function Growth Classes
Exponential Function
Needed by:
Sheet PDF
Graph PDF

Common Growth Classes


We are regularly referring to a few common growth classes.


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$.
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view