# Solving mergesort’s order of growth by induction

### Mergesort recurrence relation

$$\begin{split} T(n) = \left\{ \begin{array}{l} \Theta(1) &if\ n = 1, \\ T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n) &otherwise \end{array} \right.\ \end{split}$$

### Forming our induction hypothesis

Assume n is power of 2.

Hence, for some constant $$C \ge 0$$ we have:

$$\begin{split} T(n) \leq \left\{ \begin{array}{l} C, &if\ n = 1, \\ 2T(n/2) + Cn, &otherwise \end{array} \right.\ \end{split}$$

Next, we unfold the recurrence to provide us the intuitions:

$$\begin{split} T(n) &≤ 2(2T(n/4) + Cn/2) + Cn &= \textbf{4T(n/4) + 2Cn} \\ &≤ 4(2T(n/8) + Cn/4) + 2Cn &= \textbf{8T(n/8) + 3Cn} \end{split}$$

We observe that each step of unfolding (bolded above) follows the general form of: $$T(n) ≤ 2^kT(n/2^k) + kCn \ \textbf{for}\ 1 \leq k \leq log_{2}n - (1)$$

### Proving by induction

We want to prove statement (1) above.

For $$k = 1$$ :

$$\begin{split} T(n) &\leq 2^1T(n/2^1) + (1)Cn \\ T(n) &\leq 2T(n/2) + Cn \end{split}$$

For $$k = i$$ :

$$T(n) \leq 2^i T(n/2^i) + iCn$$

Show for $$k = i + 1$$ :

$$\begin{split} T(n) \leq 2^{i + 1} T(n/2^{i + 1}) + (i + 1)Cn \end{split}$$

Proof for $$k = i + 1$$ :

$$\begin{split} T(n) &\leq 2^i T(n/2^i) &+ iCn \\ T(n) &\leq 2^i ( 2T(n/2^{i + 1}) + Cn/2^i ) &+ iCn \\ T(n) &\leq 2^{i + 1} T(n/2^{i + 1}) &+ (i + 1)Cn \end{split}$$