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.