Given $f(n)=nlog(n)$ and $g(n)=10^{-6}n^2$, I am asked to find whether $f\in O(g)$ or $g \in O(f)$. The book claims that $f \in O(g)$, but I do not see how that is true.
If it is true, there exists a number $C$ such that
$$nlog(n) < C10^{-6}n^2$$
but this implies that
$$n^n < 2^{Mn^2} $$
where where $M = C*10^{-6}$.
This seems false to me, since $n$ can be made arbitrarily large.
I would appreciate some insight as to why I am wrong.
Note that
$$2^{Mn^2}=\left(2^{Mn}\right)^n\;,$$
and $2^{Mn}>n$ for all sufficiently large $n$.