Big-O Notation

Definition

Big-O Notation

Let $f,g:\mathbb{N}\to {\mathbb{R}}_{\ge 0}$ be functions. We say that $f$ is Big-O of $g$, written

$$f(n)\in O(g(n)),$$

if there exist constants $c>0$ and $n_0\in \mathbb{N}$ such that for all $n\ge n_0$,

$$\exists c>0:\exists n_0\in \mathbb{N}:\forall n\ge n_0:f(n)\le c\cdot g(n)$$

Limit Form

Assume that $g(n)>0$ for all sufficiently large $n$. Then

$$f(n)\in O(g(n))⟺\underset{n\to \infty }{\mathrm{limsup}}\frac{f(n)}{g(n)}<\infty .$$

If the quotient has an ordinary limit, the $\mathrm{limsup}$ (limit superior) can be replaced by $\lim$: a finite limiting ratio gives an eventual constant-factor bound.

Equality Misinterpretation

One often writes

$$f(n)=O(g(n)).$$

This is standard shorthand, but it should not be read as ordinary equality. More precisely, Big O denotes a set of functions:

$$O(g(n))=\{f:\mathbb{N}\to {\mathbb{R}}_{\ge 0}\mid \exists c>0,\exists n_0\in \mathbb{N},\forall n\ge n_0:f(n)\le c\cdot g(n)\}.$$

Thus $f(n)\in O(g(n))$ is the more literal statement.

Example

Quadratic upper bound

Let

$$f(n)=3n^2+5n+7.$$

For all $n\ge 1$,

$$3n^2+5n+7\le 3n^2+5n^2+7n^2=15n^2.$$

Hence $f(n)\in O(n^2)$ with $c=15$ and $n_0=1$.

$O$ in exponent

$$3^{n^3+4n+2}\in 3^{O(n^3+4n+2)}=3^{O(n^3)}=2^{{\log }_{2}3\cdot O(n^3)}=2^{O(n^3)}$$

Warning

$$2^{O(n^3)}\ne O(2^{n^3})$$

See The Exponent Is the Terrain.