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:
$T(n) = 2T(n/2) + cn$
$T(n/2) = 2T(n/4) + c(n/2)$
Now plug in 1. into 2.
$T(n) = 2(2T(n/4) + c(n/2)) + cn$
$T(n) = 4T(n/4) + 2cn$
Now the pattern I was able to find is the following:
- $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)$?