How does one derive $O(n \log{n}) =O(n^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.
 A: 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)$$
A: 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$.

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