Proving $n^3 \in \omega(n^2 (\log n)^2)$

Question

I have

$$n^3 > M n^2(\log n)^2$$ $$n > M (\log n)^2$$ (Since $\log n < n$.) $$n > M (n)^2$$ $$1/n > M$$ $$1/M > n$$

Therefore define n0 to be any value less than $1/M$.

But plotting the graph on Desmos does not seem correct. I think I may have gone wrong with my algebra somewhere?

Answer 1

Your first steps look good. You show that the inequality you need is equivalent to $M \log(n)^2 < n$.

After that, you use $\log(n) < n$ to conclude that if $M n^2 < n$ then you'll also get $M \log(n)^2 < n$. That is true, but it's not useful: no matter how you pick $M$, it will not be true that $M n^2 < n$ for large $n$. So you need to use a different strategy to find $M$ such that $M \log(n)^2 < n$ for all large $n$.

It's hard to hint a good strategy because I don't know what results you've proven about $\log$. But one commonly known fact is that $\log(n) \in O(n^\alpha)$ for all $\alpha > 0$. If you use this fact for $\alpha = \frac 1 4$ then you'll be able to finish your proof after a bit more algebra.

Good luck :)

---

EDIT: OP added the following in a comment: (slightly edited)

Using that I was able to get $$\begin{align} && n &> M \log(n)^2 \\ \impliedby && n &> M (n^{1/4})^2 \\ \iff && n &> M n^{1/2} \\ \iff && n^{1/2} &> M \\ \iff && n &> M^2 \end{align}$$ So then $n_0$ would be any value greater than $M^2$ ?

My response: That is almost exactly right, except you should remember the exact definition of $\log(n) \in O(n^{1/4})$. It means that there exists some $K$ and $c$ such that for all $n \ge K$, $\log(n) \le c n^{1/4}$. So your work above would be very slightly different: $$\begin{align} && n &> M \log(n)^2 \\ \impliedby && n &> M \left(c n^{1/4}\right)^2 \end{align}$$ where the last step is only valid for $n \ge K$. Now you could continue from there. At the end you'll find some condition for $n_0$ again, but then you should make sure you choose a final $n_0$ that satisfies the condition you derive AND has $n_0 \ge K$, so that this first step stays valid.