Solving time complexity of merge sort

242 Views Asked by At

I was asked to prove that the time complexity of merge sort is $ O(log_2n)$ but I cannot find a way to continue my method. Any help?

$T(n)=2T(\frac{n}{2} )+n$

$T(n)= 2[2T(\frac{n}{4})+n] +n = 4T(\frac{n}{4})+3n$

$T(n)=8T(\frac{n}{8})+7n$

$...$

$...$

$...$

$...$

$T(n)= 2^kT(\frac{n}{2^k})+(2^k-1)n$

Finally $\frac{n}{2^k}=1$ and $\therefore n=2^k$

I do not know how to continue from here to prove that it is $O(log_2n)$

1

There are 1 best solutions below

7
On BEST ANSWER

$T(n)=2T(\frac{n}{2} )+n$

$T(n)= 2[2T(\frac{n}{4})+\color{red}{\frac n2}] +n = 4T(\frac{n}{4})+\color{red}2n$

$T(n)=8T(\frac{n}{8})+\color{red}3n$

$...$

$T(n)= 2^kT(\frac{n}{2^k})+\color{red}kn$

Finally $\frac{n}{2^k}=1$ and $\therefore n=2^k$