# big theta prove

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

• Use that $\lim n^k / n^\ell \to 0$ for $k < \ell$ and $\lim n / \log(n) \to 0$. – Watercrystal Sep 8 '20 at 20:56
• 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. – plop Sep 8 '20 at 21:04
• 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. – CSch of x Sep 9 '20 at 13:00

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