# How to prove time complexity of merge sort

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)$

You can do the algebra yourself or you can just apply the master theorem http://en.wikipedia.org/wiki/Master_theorem

• With what effect? Short one-liners rarely make good Answers. Consider adding more substance to this post. – hardmath Nov 29 '14 at 0:00

It's actually n(log2n), not log2n (comparison sorts are all constrained to nlogn performance).

Looks like you're missing a division by two. Starting from the top (sorry for not knowing laTeX),

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

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

=  4 T(n/4) + 2n

= 4 [2 T(n/8) + n/4] + 2n

= 8 T(n/8) + 3n

= 2^k T(n/2^k) + kn


From your observation that n/2^k = 1 we can multiply each side by 2^k, take the log, and find log2 n = k. Inserting this into where we were before,

T(n) = 2^(log2 n)*T(1) + (log2n)*n

= n*T(1) + (log2n)*n

= n + (log2n)*n

= (log2n)*n