Big Theta: Asymptotic Tight Bound

$$ T(n) \in \Theta(f(n))\Leftrightarrow \exists \; c_1 > 0, c_2 > 0, n_0 > 0 $$

$$ s.t. \; \; c_1\cdot f(n) \le T(n) \le c_2\cdot f(n) \; \; \forall \; n \ge n_0 $$

Read it as

$T(n)$ is a member of $\Theta(f(n))$ if and only if there exist positive constants $c_1$, $c_2$ and $n_0$ such that $c_1\cdot f(n) \le T(n)\le c_2\cdot f(n)$ for all $n\ge n_0$.

$\Theta(f(n))$ is the set of functions that grow no faster and no slower than $f(n)$.

Here is a pictorial illustration of the above definition:

If you want to prove that $T(n) \in \Theta(f(n))$, you need to choose the constants $c_1$, $c_2$, and $n_0$ so that above definition holds whenever $n \ge n_0$.

Exercise The running time of an algorithm is $T(n)=7n^2+5$. Show that $T(n) \in \Theta(n^2)$.

Solution

We can choose $c_1=7$, $c_2=12$, and $n_0=1$ for the definition of Big Theta to hold.

$$ 7n^2 \le 7n^2 + 5 \le 12n^2 $$

Resources