Small-O Notation

complexity-theory

Definition

Small-O Notation

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

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

if $f$ grows strictly slower than $g$:

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

Limit form

If $g(n)>0$ eventually, then

$$f(n)\in o(g(n))⟺\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0.$$

Meaning

Small-o notation gives a strict asymptotic upper bound. Unlike Big-O notation, it does not allow $f$ to grow like a constant multiple of $g$.

Thus $f(n)\in o(g(n))$ means that $f$ eventually becomes negligible compared with $g$.

Example

Logarithmic growth is strictly below linear growth

$$\log n\in o(n),$$

because

$$\underset{n\to \infty }{\lim }\frac{\log n}{n}=0.$$