-1
$\begingroup$

Prove that $3n^3 - 6n^2 + 9n - 9\log n \in \Theta(n^3)$ using

So, how can I prove this by big theta definition? I don't what I should do with the log function

$\endgroup$
  • 1
    $\begingroup$ Use that $\lim n^k / n^\ell \to 0$ for $k < \ell$ and $\lim n / \log(n) \to 0$. $\endgroup$ – Watercrystal Sep 8 '20 at 20:56
  • $\begingroup$ You can use the inequalities $1-1/x\leq \log(x)\leq x-1$ for all $x>0$, which follow from the mean value theorem. $\endgroup$ – plop Sep 8 '20 at 21:04
  • $\begingroup$ If $\lim_{n \rightarrow \infty} | \frac{f(n)}{g(n)} | = c$ where $0 < c < \infty$ then $f(n) \in \Theta ( g(n))$ The limit is pretty easy from here. $\endgroup$ – CSch of x Sep 9 '20 at 13:00
0
$\begingroup$

Here’s a simpler approach than those suggested in the comments.

Let $f(n) = 3n^3-6n^2+9n-9\log{n}$. We wish to show $f(n) \in \Theta(n^3)$. It suffices to show $f(n) \in O(n^3)$ and $f(n) \in \Omega(n^3)$.

Big O:

We wish to show $\exists c, n_0 > 0$ such that:

$f(n) \leq cn^3$ $\forall n >n_0$.

Let $n_0 = 1.$

We have:

$f(n) = 3n^3-6n^2+9n-9\log{n} \leq 3n^3 + 9n^3 = 12n^3$. So take $c = 12$.

Big Omega:

We wish to show $\exists c, n_0 > 0$ such that:

$f(n) \geq cn^3$ $\forall n > n_0$.

Let $n_0 = 6$.

We have:

$f(n) = 3n^3-6n^2+9n-9\log{n}$

$= 2n^3 + n^2(n - 6) + 9(n - \log{n})$

$\geq 2n^3$. So take $c = 2$.

Hence, it follows $f(n) \in \Theta(n^3)$. $\Box$

$\endgroup$

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.