Small-Omega Notation

complexity-theory

Definition

Small-Omega Notation

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

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

if $f$ grows strictly faster 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 \omega (g(n))⟺\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\infty .$$

Meaning

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

Thus $f(n)\in \omega (g(n))$ means that $f$ eventually dominates $g$ by more than any constant factor.

Example

Linear growth is strictly above logarithmic growth

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

because

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