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
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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$
