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