Prove or disprove $n^2 \log{n} = O(n^2)$

Question

I'm having troubles grasping Big-Oh notation and complexities. How do I go about either proving or disproving this statement?

Answer 1

The statement is not true, but assume to the contrary that $n^2\log n = O(n^2)$. Then there exist constants $C>0$ and $n_0>0$, such that $n^2\log n \leq Cn^2$ for all $n\geq n_0$.

Divide both sides of the inequality $n^2\log n \leq Cn^2$ by $n^2$ to obtain $\log n \leq C$, which hold for all $n\geq n_0$. This is a contradiction, since $\log n$ is not a bounded function, which the inequality says that it is.

Answer 2

Let $$n=2^k$$ then, $$(n^2)logn = (2^{k^2})log_2 2^k$$ $$= k(2^{k^2})$$

And $$n^2 = 2^{k^2}$$

You can clearly see that asymptotically, $$k(2^{k^2})>2^{k^2}$$ $$\therefore (n^2)logn > n^2$$ That's why the given relation is false. But $(n^2)logn= \Omega (n^2)$ will hold true.