Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
so we can just ignore the constant if x is large enough? – AkshaiShah Jan 9 '13 at 21:34
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.