Exercise IIX

Consider the following function $T(n)$ describes the precise running time of an algorithm:

$$ T(n) = 3n^2 - 100n + 6 $$


Exercise Prove $T(n) \in \Theta(n^2)$.

Solution

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

Exercise Prove $T(n) \notin \Theta(n)$.

Solution

We have shown earlier that $T(n) \in Omega(n)$ but $T(n) \notin O(n)$. Therefore, we can conclude $T(n) \notin \Theta(n)$.

Exercise Prove $T(n) \notin \Theta(n^3)$.

Solution

We have shown earlier lessons that $T(n) \in O(n^3)$ but $T(n) \notin \Omega(n^3)$. Therefore, we can conclude $T(n) \notin \Theta(n^3)$.