1
$\begingroup$

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

Improve this question
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ With what effect? Short one-liners rarely make good Answers. Consider adding more substance to this post. $\endgroup$ – hardmath Nov 29 '14 at 0:00
2
$\begingroup$

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
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.