Big-O Notation

complexity-theory

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)$$

Notation

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 cg(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$.