Why does merge sort run in $O(n^2)$ time?

Question

I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O is the upper bound running time/space of the algorithm, Big Omega is the lower bound running time/space of the algorithm and Big Theta is like the in between of the two.

This particular answer on SO stumbled me with the following statement

For example, merge sort worst case is both ${\cal O}(n\log n$) and $\Omega(n\log n)$ - and thus is also $\Theta(n\log n)$, but it is also ${\cal O}(n^2)$, since $n^2$ is asymptotically "bigger" than it. However, it is NOT $\Theta(n^2)$, Since the algorithm is not $\Omega(n^2)$

I thought merge sort is ${\cal O}(n\log n)$ but it seems it is also ${\cal O}(n^2)$ because $n^2$ is asymptotically bigger than it. Can someone explain this to me?

Answer 1

This is actually a mathematical matter and not the matter of the worst case running time. First you have to know that Big O does not represent worst case running time of some algorithms. Big O comes from mathematics and it represents an asymptotic upper bound for some mathematical functions.

You can see that the graph of $n^2$ is always above the graph of $n\log n$. so you can say $n^2$ is an upper bound on $n\log n$ as the value of $n\log n$ is always less than $n^2$. So mathematically you can say $n\log n=O(n^2)$. Similarly graphs of all $n^i$ for $i\geq 2$ are always above the graph of $n\log n$. So you can say $n\log n$ is also $O(n^3),O(n^4),O(n^5),\ldots$

But one thing you have to remember that though $n\log n$ is $O(n^2)$ but $n\log n$ is not $\Theta(n^2)$, because $n\log n$ is not $\Omega(n^2)$. Mathematically you can say $n\log n$ is $o(n^2)$.

If you still have any confusion regarding my answer, you can ask me here.

Answer 2

Let's consider a simpler situation. For numbers $x,y$, say that $x = S(y)$ if $x \leq y$, that $x = L(y)$ if $x \geq y$, and that $x = E(y)$ if both $x = S(y)$ and $x = L(y)$. Since $1 = S(1)$ and $1 = L(1)$, it is the case that $1 = E(1)$. But it is also the case that $1 = S(2)$.

The situation with running times is similar. Given two positive functions $f,g$, we say that $f = O(g)$ if $f(n) \leq Cg(n)$ for some $C > 0$ (independent of $n$), that $f = \Omega(g)$ if $f(n) \geq cg(n)$ for some $c > 0$, and that $f = \Theta(G)$ if $f = O(g)$ and $f = \Omega(g)$. For example $2n = O(n)$ since $2n \leq 2 \cdot n$ and $2n = \Omega(n)$ since $2n \geq n$, and so $2n = \Theta(n)$. It is also the case that $2n = O(n^2)$ since $2n \leq 2\cdot n^2$.

For numbers we have the important property of transitivity: $x \leq y \leq z$ implies $x \leq z$. The same relation holds for functions: if $f = O(g)$ and $g = O(h)$ then $f = O(h)$; indeed, if $f \leq C_1 g$ and $g \leq C_2 h$ then $f \leq C_1C_2 h$. The running time of merge sort $T(n)$ is $\Theta(n\log n)$, and $n\log n = O(n^2)$, and so $T(n) = O(n^2)$, but $T(n)$ is not $\Omega(n^2)$ and so $T(n)$ is not $\Theta(n^2)$. The class $\Theta(n\log n)$ is a tight bound on $T(n)$; $O(n^2)$ is an upper bound which is not tight.

Answer 3

Intuitively, $f=\cal O(g)$ means that $f$ grows no faster than $g$. Clearly, $n \log n$ grows no faster than $n^2$ and we can write $n \log n = \cal O(n^2)$. Symmetrically, $f=\cal \Omega(g)$ means that $f$ grows at least as fast as $g$. $n \log n$ does not grow at least as fast as $n^2$ so we have the inequality $n \log n \neq \cal \Omega (n^2)$. When $f$ grows no faster than $g$ and at least as fast as $g$, it makes sense to say that $f$ grows as fast as $g$; write $f=\cal \Theta(g)$.

To answer your question, notice that grows no faster than is transitive. For numbers $x,y,z$ we all know that if $x\lt y$ and $y\lt z$ then this implies that $x\lt z$. Now for functions $f,g,h$, we have that if $f=\cal O(g)$ and $g=\cal O(h)$ then this implies that $f=\cal (h)$. Let $f=\cal O(n\log n)$. Since $n \log n = \cal O(n^2)$, we have that $f = \cal O(n^2)$.

This should hopefully help you better understand Big O notation. You can prove transitivity of $\cal O$ using the formal definition:

For functions $f,g$, we say that $f$ is Big O of $g$ (write $f=\cal O(g)$) if there exist constants $n_0,c \gt 0$ such that $f\le c\times g$ whenever $n\ge n_0$.

This means that starting at some point along the $x$ axis (we call it $n_0$) the function $f$ is always bounded above by a constant multiple of $g$.

Answer 4

I do not find any contradiction between your (said) understanding and the answer from StackOverflow you posted. It seems your problem is at the level of your understanding of upper bound and lower bound.

In this context of algorithm complexity, upper bound means cannot be asymptotically worse than. As such all algorithms are $O(\infty)$. Lower bound means cannot be asymptotically better than. As such all algorithms are $\Omega(0)$.

However for those algorithms for which there exists an $O(f(n))$ and an $\Omega(f(n))$, where $f(n)$ is some function of $n$, there also exists a $\Theta(f(n))$. So we notice that of the three only $\Theta$ is unique.