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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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$.
You are correct in thinking it works like a less than or equal.