Definition:Theta Notation/Informal Definition
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.
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 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.
Also see
- Results about $\Theta$ notation can be found here.
Sources
- 1990: Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest: Introduction to Algorithms ... (previous) ... (next): $2$: Growth of Functions: $2.1$ Asymptotic Notation: $\Theta$-notation