Merge Sort proof [duplicate]

Question

I am trying to prove that merge sort is indeed $O(n \log n)$.

I was able to extract a pattern using constants, however now I am stuck. This is as far as I can get:

1. $T(n) = 2T(n/2) + cn$

2. $T(n/2) = 2T(n/4) + c(n/2)$

Now plug in 1. into 2.

3. $T(n) = 2(2T(n/4) + c(n/2)) + cn$

4. $T(n) = 4T(n/4) + 2cn$

Now the pattern I was able to find is the following:

5. $2^kT(n/2^k) + kcn$

Is there a way to use this pattern to prove that merge sort has complexity of $O(n\log n)$?

Answer 1

You correctly figured out that after unrolling the recursive equation $$T(n) = 2 \cdot T(n/2) + c n$$ $k$-times you get $$T(n) = 2^k \cdot T(n/2^k) + k c n.$$ To finish your proof, ask yourself when the unrolling process will stop. The answer: when we reach the base case, which is $T(1) = d$ where $d$ is a constant. For what value of $k$ do we reach $T(1)$? For this we need to solve the equation $$n/2^k = 1$$ whose solution is $k = \log_2 n$. So now we plug in $k = \log_2 n$: \begin{align*} T(n) &= 2^{\log_2 n} \cdot T(n/2^{\log_2 n}) + c \cdot n \cdot \log_2 n \\ &= n \cdot T(1) + c \cdot n \cdot \log_2 n \\ &= d \cdot n + c \cdot n \cdot \log_2 n \\ &\in O(n \cdot log_2 n). \end{align*}