Big O Notation

complexity-theory

Definition

Big O Notation

The Big O notation is a notation for analysing the asymptotic complexity of a program or algorithm.

The notation is used to describe the lower and upper bounds of the runtime $T(n)$ of a program for an input size $n>n_0$:

$$c_1\cdot g(n)\le T(n)\le c_2\cdot f(n)$$

where $g(n)$ is the lower bound, $f(n)$ is the upper bound and $n_0$ is the smallest input size for which the runtime is not negligible.

To simplify the notation, we can express the runtime in terms of $g(n)$ and $f(n)$ as follows:

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

which is sometimes also expressed using the notation $T(n)=O(f(n))$, which must not be interpreted as equality.

If the upper bound $f(n)$ is equal to the lower bound $g(n)$, then we can say that:

$$T(n)\in \Theta (f(n))$$

Schematic Foundation

Boundedness

$$g(n)\le T(n)\le f(n)$$

where $g(n)$ is the lower bound, $T(n)$ is the runtime and $g(n)$ is the upper bound.

Neglect Constant Factors

We are allowoed to add a constant factor $c_1$ to the lower bound and a constant factor $c_2$ to the upper bound to constraint the runtime $T(n)$.

$$c_1\cdot g(n)\le T(n)\le c_2\cdot f(n)$$

Neglect Small Input Sizes

We can specify a minimum input size $n_0$ for which (below) the runtime is not negligible.

$$\forall n>n_0:c_1\cdot g(n)\le T(n)\le c_2\cdot f(n)$$

Properties

Additivity

If $f=O(h)$ and $g=O(h)$, then it holds that $f+g=O(h)$, where

$$(f+g)(n)=f(n)+g(n)$$

Dominance

$$1\ll \log n\ll \sqrt{n}\ll n\ll n\log n\ll n^{1+\epsilon }\ll n^2\ll n^3\ll n^k\ll c^n\ll n!\ll n^n$$

where $c>1$, $k>3$, $0<\epsilon <1$ .

todo