Big Theta: Another Definition!

$T(n) \in \Theta(f(n))$ if and only if $T(n) \in O(f(n))$ and $T(n) \in \Omega(f(n))$.

Note that Big Theta describes a tight bound. So it is a stronger statement than Big-Oh and big Omega.

Another method of determining the condition is the following limit:

$$ \lim_{n\rightarrow \infty} \frac{T(N)}{f(n)} = c, \; \; \text{where} \; \; 0 < c < \infty $$

If such a $c$ does exist, then $T(n) \in \Theta(f(n))$.

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

Solution

We have shown earlier that $T(n) \in O(n^2)$ and $T(n) \in \Omega(n^2)$. Therefore, we can conclude $T(n) \in \Theta(n^2)$. Also, we can show:

$$ \lim_{n\rightarrow \infty} \frac{7n^2 + 5}{n^2} = 7 $$