Definition:Theta Notation
Definition
Informal Definition
Let $f: \N \to \R$ and $g: \N \to \R$ be real sequences, expressed as real-valued functions on the set of natural numbers $\N$.
- $f$ is $\Theta$ of $g$
- there exist positive constants $c_1$ and $c_2$ such that $\map f n$ can be "sandwiched" between $c_1 \map g n$ and $c_2 \map g n$ for sufficiently large $n \ge n_0$.
It is not as important to determine the values of $c_1$, $c_2$ as it is to establish that such constants exist.
Definition 1
Let $g: \N \to \R$ be a real sequence, expressed here as a real-valued function on the set of natural numbers $\N$.
Then $\map \Theta g$ is defined as:
- $\map \Theta g = \map \OO g \cap \map \Omega g$
where:
- $\map \OO g$ is big-$\OO$ notation
- $\map \Omega g$ is big-$\Omega$ notation.
That is:
- $\map \Theta g = \set {f: \N \to \R: \exists c_1, c_2 \in \R_{>0}: \exists n_0 \in \N: \forall n > n_0: 0 \le c_1 \cdot \size {\map g n} \le \size {\map f n} \le c_2 \cdot \size {\map g n} }$
Definition 2
Let $f: \N \to \R, g: \N \to \R$ be two real sequences, expressed here as real-valued functions on the set of natural numbers $\N$.
Let there exist $c \in \R_{>0}$ such that:
- $\ds \lim_{n \mathop \to \infty} \frac {\map f n} {\map g n} = c$
Then:
- $\map f n \in \map \Theta {\map g n}$
Notation
The expression $\map f n \in \map \Theta {\map g n}$ is read as:
- $\map f n$ is theta of $\map g n$
While it is correct and accurate to write:
- $\map f n \in \map \Theta {\map g n}$
it is a common abuse of notation to write:
- $\map f n = \map \Theta {\map g n}$
This notation offers some advantages.
Also defined as
Sources which utilise order notation so as to explore the behaviour of algorithms are concerned only with algorithm run times, necessarily positive.
Hence they may define the $\Theta$ notation on positive real sequences only, as follows:
Let $g: \N \to \R$ be a real sequence, expressed here as a real-valued function on the set of natural numbers $\N$.
Then $\map \Theta g$ is defined as:
- $\map \Theta g = \set {f: \N \to \R: \exists c_1, c_2 \in \R_{>0}: \exists n_0 \in \N: \forall n \ge n_0: 0 \le c_1 \cdot \map g n \le \map f n \le c_2 \cdot \map g n}$
Some sources define some or all of the inequalities in this expression to be strict, that is:
- $\map \Theta g = \set {f: \N \to \R: \exists c_1, c_2 \in \R_{>0}: \exists n_0 \in \N: \forall n > n_0: 0 \le c_1 \cdot \map g n < \map f n < c_2 \cdot \map g n}$
Also known as
Some sources refer to $\Theta$ notation as big-$\Theta$ notation, in parallel with big-$\OO$ and big-$\Omega$.
However, it is worth bearing in mind that:
and so there is no need to distinguish between big-$\Theta$ and little-$\theta$.
Hence $\mathsf{Pr} \infty \mathsf{fWiki}$ consistently use the term $\Theta$ notation, voicing it as theta notation.
Motivation
$\Theta$ notation is a type of order notation for typically comparing run-times or growth rates between two growth functions.
$\Theta$ is a stronger statement than big-$\OO$ and big-$\Omega$.
Examples
Arbitrary Example $1$
Theta Notation/Examples/Arbitrary Example 1
Also see
- Results about $\Theta$ notation can be found here.