2

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.

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

4 Answers4

6

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)$$

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

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$.
not all wrong
  • 16,178
  • 2
  • 35
  • 57
2

$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)$.

CBenni
  • 1,940
  • 1
    You're talking about Big O but using little o's? – Pedro May 29 '13 at 17:57
  • @PeterTamaroff, no, I am talking about little o's, im just used to calling the entire subject BigO notation ;) – CBenni May 29 '13 at 17:58
  • 1
    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. – Pedro May 29 '13 at 18:00
  • @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. – CBenni May 29 '13 at 23:10
1

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.

Najib Idrissi
  • 54,185
  • but why only n^2?can we use some other constant? – nikhil May 29 '13 at 18:04
  • @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})$. – Adriano May 29 '13 at 18:06