Big-Omega Notation

complexity-theory

Definition

Big-Omega Notation

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

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

if $f$ is eventually at least a constant multiple of $g$:

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

Meaning

Big-Omega notation gives an asymptotic lower bound. It says that after some finite threshold $n_0$, the function $f$ never grows slower than a constant multiple of $g$.

It is dual to Big-O notation:

$$f(n)\in \Omega (g(n))⟺g(n)\in O(f(n)).$$

Example

Quadratic lower bound

Let

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

For all $n\ge 1$,

$$f(n)\ge 3n^2.$$

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