Definition:Big-Theta

From ProofWiki
Jump to: navigation, search

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))$.