2
$\begingroup$

I was studying time complexity where I found that time complexity for sorting is $O(n\log n)=O(n^2)$. Now, I am confused how they found out the right-hand value. According to this $\log n=n$. So, can anyone tell me how they got that value?

Here is the link where I found out the result.

$\endgroup$
  • 1
    $\begingroup$ Why aren't editors checking the link before changing big O to little O? The link clearly uses big O. $\endgroup$ – Pedro Tamaroff May 29 '13 at 18:14
  • 1
    $\begingroup$ The "accepted" answer deals with little-o asymptotics although the question is about Big-O asymptotics. OP: can you explain? $\endgroup$ – Did May 29 '13 at 18:47
  • $\begingroup$ @Did I was about to ask the very same thing. $\endgroup$ – Pedro Tamaroff May 29 '13 at 19:20
  • $\begingroup$ @PeterTamaroff Priority attribution: you mentioned all this, well before my comment... $\endgroup$ – Did May 29 '13 at 19:24
2
$\begingroup$

$f(x)=\mathcal{O}(g(x))$ means that $f$ is asymptotically smaller or equal to $g$. This means that $|f(x)|\le c|g(x)|\quad \forall x$ for some constant c.

Now in your example, $$n\log n \le n^2$$

This does not say that $n=\log n$, but instead, that $\log n\le n$. In other words, that $\log n$ is asymptotically smaller or equal to $n$, or, in Big-O notation, $\log n = \mathcal{O}(n)$.

$\endgroup$
  • 1
    $\begingroup$ You're talking about Big O but using little o's? $\endgroup$ – Pedro Tamaroff May 29 '13 at 17:57
  • $\begingroup$ @PeterTamaroff, no, I am talking about little o's, im just used to calling the entire subject BigO notation ;) $\endgroup$ – CBenni May 29 '13 at 17:58
  • 1
    $\begingroup$ OK, but the OPs question is about $n\to\infty$ and sequences and Big O, not functions and quotients and Little O. You seem to have missed this. $\endgroup$ – Pedro Tamaroff May 29 '13 at 18:00
  • $\begingroup$ @PeterTamaroff I didnt. I answered the OPs question in the last line. I avoided the formal definition using quantors for the exact reason that I assumed that that was what the OP hadnt understood. $\endgroup$ – CBenni May 29 '13 at 23:10
6
$\begingroup$

No, $O(n\log n)=O(n^2)$ doesn't mean $\log n=n$.

Recall that $f(n)=O(g(n))$ means there exists $C$ and $N$ such that $|f(n)|\leq C g(n)$ for $n\geq N$. For example, $\log n$ is $O(n)$. Thus, $n\log n$ is $O(n^2)$.

What I guess they are trying to say is that if something is $O(n\log n)$ then it is $O(n^2)$, that is $n\log n$ is $O(n^2)$. Note that the reverse usage $$O(n^2)=O(n\log n)$$ would be incorrect. A better notation might be $$O(n\log n)\subseteq O(n^2)$$

$\endgroup$
  • 7
    $\begingroup$ +1 - this is exactly why I much, much prefer the subset language ($\subseteq$ and $\in$) for questions about big-O and related notations. $\endgroup$ – Steven Stadnicki May 29 '13 at 18:14
2
$\begingroup$

That's not what $O$ means!

When people write $f(x) = O(g(x))$ (for large $x$) they're not saying something about the specific, exact form of $f$. What this notation means is that there's some (possibly unknown number) $M$ such that $$|f(x)| \le M |g(x)|$$ for all big enough $x$. Intuitively,

$f(x)$ is no bigger than $g(x)$ for large $x$ - at least up to a constant factor.

In this case, they're saying that

  • the number of steps sorting takes is no more than $\text{something}\times n\log n$.
  • the function $n\log n$ isn't any bigger than $An^2$ for large $n$, for some $A$.
$\endgroup$
1
$\begingroup$

What this equation means is that the class $O(n\log n)$ is included in the class $O(n^2)$. That is, if a sequence is eventually bounded above by a constant times $n \log n$, it will eventually be bounded above by a (possibly different) constant times $n^2$. Can you prove this? The notation is somewhat surprising at first, yes, but you get used to it.

$\endgroup$
  • $\begingroup$ but why only n^2?can we use some other constant? $\endgroup$ – nikhil May 29 '13 at 18:04
  • $\begingroup$ @nikhil Yes. In fact, $O(n \log n) = O(n^{1+\epsilon})$ for any $\epsilon>0$. So for example, we have $O(n \log n) = O(n^{3})$ and $O(n \log n) = O(n^{1.5})$ and $O(n \log n) = O(n^{1.0000001})$. $\endgroup$ – Adriano May 29 '13 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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