Big-Theta Notation

complexity-theory

Definition

Big-Theta Notation

Let $f,g:\mathbb{N}\to {\mathbb{R}}_{\ge 0}$ be functions. We say that $f$ is Big-Theta of $g$, written

$$f(n)\in \Theta (g(n)),$$

if $f$ is bounded above and below by constant multiples of $g$:

$$\exists c_1>0\exists c_2>0\exists n_0\in \mathbb{N}\forall n\ge n_0:c_{1}g(n)\le f(n)\le c_{2}g(n).$$

Meaning

Big-Theta notation gives an asymptotically tight bound. It says that $f$ and $g$ have the same growth rate up to constant factors.

Equivalently,

$$f(n)\in \Theta (g(n))⟺f(n)\in O(g(n))\text{ and }f(n)\in \Omega (g(n)).$$

Example

Tight quadratic bound

Let

$$f(n)=3n^2+5n+7.$$

Then

$$f(n)\in \Theta (n^2),$$

because $f$ is bounded above and below by constant multiples of $n^2$ for all sufficiently large $n$.