Merge Sort time complexity analysis

HINT:

Use induction to show that there are constants $c$ and $n_0$ s.t. $T(n) \leq c \cdot n \log n \quad\forall n \geq n_0$. Use $T(2)$ as your base case. Remember cool log properties to reduce the logarithm and to use the induction hypothesis.

Post your progress if you get stuck.

Let $L(k)=T(2^k)$ and $n = 2^k$. Then $L(k)=T(n)$, $L(k-1)=T(n/2)$, and thus, $$ L(k)=2L(k-1)+2^k\tag1 $$ Multiplying $(1)$ by $2^{-k}$ gives $$ \overbrace{2^{-k}L(k)}^{a_k}=\overbrace{2^{-(k-1)}L(k-1)}^{a_{k-1}}+1\tag2 $$ Iterating $(2)$, we get $$ 2^{-k}L(k)=L(0)+k\tag3 $$ which means $$ L(k)=2^k(L(0)+k)\tag4 $$ which is $$ T(n)=n(T(1)+\log(n))\tag5 $$ Therefore, $T(n)=O(n\log(n))$.

T(1) = 1

T(n) = 2T (n/2) + cn

T(n) = 2T (n/2) + cn

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

T(n) = 2 [ 2T (n/4) + c (n/2) ] + cn

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

Similary, T(n) = 8T (n/8) + 3cn

General T(n) = 2^k T (n/2^K) + kcn

(n/2^k) = 1

n = 2^k

k = log base2 n

plug in k into the general formula

T(n) = n T(1) + logBase2n cn

T(n) = Big Thetha(n log n )