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

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?

• possible duplicate of Sorting functions by asymptotic growth – D.W. Mar 16 '14 at 1:58
• For mergesort, you even have a bound $O(2^n)$. It is an upper bound, nobody said it is in any way "best possible". – vonbrand Mar 16 '14 at 2:39
• We both agree that $10 < 20$. Also, $10 < 30$. In much the same way, $f(n)$ can be $O(g(n))$ and $O(h(n))$ at the same time. On the other hand, if $x = y$ and $x = z$, we know also $y = z$. Similarly, if $f(n)$ is $\Theta(g(n))$ and $\Theta(h(n))$, we know $g(n)$ is $\Theta(h(n))$ and $h(n)$ is $\Theta(g(n))$. – Patrick87 Mar 16 '14 at 13:57
• O(n^2) does not necessarily mean running time would be O(n^2).It Just mean running time is less than or equal to O(n^2).in this case O(n^2) represents that running time would be less than O(n^2) as it is not asymptotically tight.For further details see my answer. – tanmoy Mar 16 '14 at 14:22
• All answers are available in our reference questions on asymptotics. – Raphael Apr 12 '14 at 17:53

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.

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.

• Does this mean that the worst possible running time for mergesort is O(nlogn) but the possible running time for mergesort is O(infinity) ?? – Computernerd Mar 16 '14 at 12:58
• Not at all. The running time $T(n)$ of mergesort is bounded by $cn\log n \leq T(n) \leq Cn\log n$ for some constants $0<c<C$. – Yuval Filmus Mar 16 '14 at 15:00

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

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.