Definition:Big-Omega

Definition

Big-Omega notation is a type of order notation for typically comparing 'run-times' or growth rates between two growth functions.

Let $f, g$ be two functions.

Then:

$f \left({n}\right) \in \Omega \left({g \left({n}\right)}\right)$

iff:

$\exists c > 0, k \ge 0: \forall n > k: f \left({n}\right) \ge c g \left({n}\right)$

This is read as:

$f \left({n}\right)$ is big omega of $g \left({n}\right)$.

Another method of determining the condition is the following limit:

$\displaystyle \lim_{n \to \infty} {\frac{f \left({n}\right)} {g \left({n}\right)}} = c > 0$

where $0 < c \le \infty$.

If such a $c$ does exist, then:

$f \left({n}\right) \in \Omega \left({g \left({n}\right)}\right)$

To say that $f \left({n}\right) \in \Omega \left({g \left({n}\right)}\right)$ is equivalent to:

$g \left({n}\right) \in \mathcal O \left({f \left({n}\right)}\right)$

where $\mathcal O$ is the big-O notation.

Also see

• Definition:O Notation
• Definition:Little-Omega