# Proving Big-Theta

I am having trouble understanding the Big-Theta definition and providing a proof.

Prove that $$4n^3 + 3n^2 +2n - 5$$ is $$\Theta(n^3)$$.

I believe using the definition the set up would be as followed:

Proof: By Big-Theta Definition Let the above expression be denoted as $$T(n)$$. $$T(n)$$ is $$\Theta(n^3)$$ if $$c_1*n^3 \leq |T(n)| \leq c_2*n^3$$ for some $$n >= n_0$$.

This part of solving I am having trouble with:

How do I solve each side to prove that T(n) exists both in $$O(n^3)$$ and $$\Omega(n^3)$$?

• You can exhibit examples of $c_1$ and $c_2$. Then try to find $n_0$ such that both inequalities are satisfied for all $n\geq n_0$. For example, you will be able to do this for $c_1=3$ and $c_2=5$. The two inequalities that you get are $0\leq n^3+3n^2+2n-5$ and $0\leq n^3-3n^2-2n+5$. You have freedom of taking $n_0$ as large as you need. For example, $n_0=1+3+2+5$ should be ok. If $n\geq11$, then $n^3\pm3n^2\pm2n\pm5\geq n^2(n-3-2-5)\geq0$.
– plop
Oct 8, 2020 at 16:03

From one hand $$4n^3 + 3n^2 +2n - 5<4n^3+3n^3 +2n^3=9n^3$$ so for big-$$O$$ you have $$c_2=9, n_0=1$$.
From another hand $$4n^3 + 3n^2 +2n-5\geqslant 4n^3$$ when $$3n^2 +2n-5\geqslant 0$$, so for big-$$\Omega$$ you have $$c_1=4, n_0=1$$.