Exercise IIX

  • Use the definition of Big Theta to show the asymptotic running time of a given program.

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

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


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

Solution

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

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

Solution

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

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

Solution

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