# Proving merge sort is $O(n^2)$ using induction

I'm trying to show that merge sort is $O(n^2)$ using induction. (I'm just concerned with powers of two for simplicity). However, I'm stuck at the last inequality

Basis step:

Show that there exists a constant $C$ for all $n=2$ such that: \begin{align*}M(2) &\leq C \cdot (2)^2\\ 1 &\leq 4C \\\end{align*}\\ \therefore \text{holds for n=2 with C \geq \frac{1}{4}}

Inductive Hypothesis:

There exists a constant $C$ for all $n>1$ such that: $$M(n) \leq C \cdot n^2$$

Inductive step:

There exists a constant $C$ for all $n>1$ such that: \require{cancel}\begin{align*} M(2n) &\leq C \cdot (2n)^2 \\ \text{Show that: }\\ M(2n) &\leq C \cdot 4n^2 \\ 2 \cdot M(n)+2n &\leq C \cdot 4n^2 \tag{Recurence relation} \\ 2 \cdot M(n) &\leq C \cdot 4n^2 - 2n \\ \cancel{2}(M(n)) &\leq \cancel{2}(C \cdot 2n^2 - n) \\ M(n) &\leq C \cdot 2n^2 - n \\\end{align*}

From here if I can show that $C\cdot n^2 \leq C \cdot 2n^2 - n$ then using the Inductive hypothesis ($M(n) \leq C \cdot n^2$) I can show that the proof holds.

How do I show $C\cdot n^2 \leq C \cdot 2n^2 - n$? And how do I find the min value of $C$ where this holds?

• Your inductive proof is a little backwards. You're starting with what you want to prove, not something that you know is true. If you start with the inductive hypothesis, and work backwards, you'll need the inequality $C\cdot n^2\leq C\cdot 2n^2-n$, which is easier to prove, because it's true. Apr 7 '15 at 10:12
• Thank you, I've updated the question to clarify Apr 7 '15 at 10:26

How do I show $C\cdot n^2 \le C\cdot 2n^2−n$? And how do I find the min value of $C$ where this holds?

There are two things you need to find: any positive $n_0$ and any positive $C$ such that your above relation holds for $n>n_0$.

It doesn't have to hold for all $n$: it only has to hold for "sufficiently large" $n$. And you don't need to find the minimum $C$. The "minimum" $C$ will depend on which $n_0$ you chose anyway.

The easy way to do it is just pick an arbitrary value of $C$, such as $C=1$ and ask when is $n^2 \le 2n^2 - n$ ? Answer, for $n \ge 1$. So one solution is $C=1$, $n_0 = 1$.

If you want to find all possible witnesses to $C$ and $n_0$, then solve:

$$C\cdot n^2 \le C\cdot 2n^2−n$$ $$n \le Cn^2$$ $$1 \le Cn$$

So any value of $C$ and $n_0 \ge \frac{1}{C}$ will satisfy the relation.

Note that $O(n^2)$ isn't a tight upper bound on mergesort, you could prove that it is $O(n~\log(n))$ as well.