Question

Show directly that \(f(n)=n^{2}+3 n^{3} \in \Theta\left(n^{3}\right) .\) That is, use the definitions of \(O\) and \(\Omega\) to show that \(f(n)\) is in both \(O\left(n^{3}\right)\) and \(\Omega\left(n^{3}\right)\)

Short answer

Function \(f(n) = n^{2}+3 n^{3}\) is \(O(n^{3})\) and \(\Omega(n^{3})\), and therefore it is also \(\Theta(n^{3})\).

Step-by-step solution

Proving \(f(n)\) is \(O(n^{3})\)

First, we have to prove \(f(n)\) is \(O(n^{3})\). The definition of Big-O notation says: \(f(n) = O(g(n))\) means there are positive constants \(c\) and \(n_{0}\) such that \(0 \leq f(n) \leq c\cdot g(n)\), for all \(n > n_{0}\). We can see that for \(n^{3}\), the function \(f(n)=n^{2}+3 n^{3}\) will always be less than or equal to \(4n^{3}\), for all \(n > 1\). So here, \(c = 4\) and \(n_{0} = 1\). Hence \(f(n) = O(n^{3})\).

Proving \(f(n)\) is \(\Omega(n^{3})\)

Next, we have to prove that \(f(n)\) is \(\Omega(n^{3})\). The definition of Big-Omega notation says: \(f(n) = \Omega(g(n))\) means there are positive constants \(c\) and \(n_{0}\) such that \(0 \leq c\cdot g(n) \leq f(n)\), for all \(n > n_{0}\). We can see that for \(n^{3}\), the function \(f(n)=n^{2}+3 n^{3}\) will always be greater than or equal to \(n^{3}\), for all \(n > 1\). So here, \(c = 1\) and \(n_{0} = 1\). Hence \(f(n) = \Omega(n^{3})\).

Conclusion that \(f(n)\) is \(\Theta(n^{3})\)

Since \(f(n)\) is both \(O(n^{3})\) and \(\Omega(n^{3})\), we can conclude that \(f(n) = \Theta(n^{3})\). The function is bounded both above and below by \(n^{3}\), so it is \(\Theta(n^{3})\).