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. 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 $$