# Definition:Big-Omega

Jump to navigation
Jump to search

## 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.