0
$\begingroup$

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)$?

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – plop
    Commented Oct 8, 2020 at 16:03

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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