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!


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.