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. Handle n to be power of 2 in recurrence relation

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