Definition:Big-Theta

Definition

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

Big-Theta is a stronger statement than Big-O and Big-Omega.

Suppose $f: \N \to \R, g: \N \to \R$ are two functions.

Then:

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

iff:

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

where $O \left({g \left({n}\right)}\right)$ is Big-O and $\Omega \left({g \left({n}\right)}\right)$ is Big-Omega.

This is read as "$f \left({n}\right)$ is big-theta 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$, where $0 < c < \infty$

If such a $c$ does exist, then $f \left({n}\right) \in \Theta (g \left({n}\right))$.