0

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.

J. Dunivin
  • 3,103

1 Answers1

2

Note that

$$2^{Mn^2}=\left(2^{Mn}\right)^n\;,$$

and $2^{Mn}>n$ for all sufficiently large $n$.

Brian M. Scott
  • 616,228