Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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)$. –  Danikar Jan 9 '13 at 21:40

Your Answer

 
discard

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.