# Big 0h question how are they similar?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal to, but I am not fully sure. Any have any ideas? Thanks.

-

We say that $f(x)$ is $O(g(x))$ if there exists a positive constant $M$ and $x_0$ such that $f(x) \le Mg(x)$ for $x \ge x_0$.
So if a function $f(x)$ is $O(n\log n)$, it would be $O(n^2)$ since $f(x) \le Mx\log x \le Mx^2$ for some $M$ and sufficiently large $x$.
If you are referring to $M$, that is part of the definition and must exist. So you cannot really ignore it. If you are talking about why you can throw out a constant like $k$ in $O(kn^2)$, it is because we can make $M$ large enough so that $kn^2 < Mn^2$, so $O(kn^2) = O(n^2)$. – zrbecker Jan 9 '13 at 21:40