Im working on the Big-O notation and struggle to understand whether I have done enough to prove the following:
$5n^3+4n^2+4 \in \Theta (n^3)$
So based on the definition of $Θ(g(n)):$
Step $1$: $0 ≤ c_1 n^3 \leq 5n^3+4n^2+4 \leq c_2 n^3$
Divide the inequality by the largest order n-term
Step $2$: $0 ≤ c_1 \leq 5+(4/n+4/n^3) \leq c_2$
Find constant $c_2$ that will satisfy:
Step $3$: $0 \leq 5+(4/n+4/n^3) \leq c_2$
For $n=1$, $0 \leq 5+(4/1+4/1^3)=13$
For $n=2$, $0 \leq 5+(4/2+4/2^3)=7,5$
For $n=3$, $0 \leq 5+(4/3+4/3^3)=6,7$
For $n=4$, $0 \leq 5+(4/4+4/4^3)=6,06$
Since $c_2$ approaches $5$ when $n \to \infty$, I pick 5 for $c_2$ as it satisfies the equation in Step $3$
Step $4$: Is to find $c_1$
Since $c_1$ can be $\leq 5$
I can say that $5n^3+4n^2+4 \in \Theta (n^3)$ for $c_1$ $\leq 5$ and $c_2 \geq 5$. However not sure how to find $n_0$ in that regard.
Appreciate any insights!
Best Answer
Hint: $1 \le n^2 \le n^3$ for $n \ge 1\,$, so $5n^3 \;\le\; 5n^3+4n^2+4 \;\le\; 5n^3+4n^3+4n^3 = 13 n^3\,$.