Question
Given the recurrence relation for the Merge Sort algorithm:
$T(n) = 1$, if $n = 1$
$T(n) = 2T(n/2) + n$, if $n > 1$
Prove by induction that $T(n) = n\log(n) + n$ and hence $O(n\log(n))$
My solution so far:
1. Basis
$T(1) = 1$
$T(1) = 1\log(1)+1 = 0+1 = 1$
Thus we have established our basis
2. Induction Hypothesis
Assume that $T(k) = k\log(k)+k$ is true
3. Induction Step
We want to show that $T(k+1) = (k+1)\log(k+1)+(k+1)$
$T(k+1) = 2T((k+1)/2) + (k+1)$
? ? ?
$T(k+1) = (k+1)\log(k+1)+(k+1)$