I'm reading a proof on the time complexity of MergeSort which makes this statement without any justification. I've tried to show it myself but I'm not getting far; these are my steps so far.

$\sum\limits_{i=0}^{\lg(n)-1} \theta(\frac{n}{2^i}) =\theta(n\sum\limits_{i=0}^{\lg(n)-1}\frac{1}{2^i})$

Now $\sum\limits_{i=0}^{\infty}\frac{1}{2^i} = 2$, so $\sum\limits_{i=0}^{\lg(n)-1}\frac{1}{2^i} \leq 2$. This means that $\theta(n\sum\limits_{i=0}^{\lg(n)-1}\frac{1}{2^i}) = \theta(2n) = \theta(n)$, but surely not. Where is my logic wrong?

  • 3
    $\begingroup$ You got a wrong equation to solve at the very start. The recurrence of MergeSort is $T(n) = 2T(n/2) + n$. By expanding it carefully, you will find that you have missed a factor $2^i$ for the summand. $\endgroup$
    – hengxin
    Apr 6 '15 at 13:13
  • $\begingroup$ The proof shows through unwinding the recurrence that the running time of MergeSort is $\theta(n) + \sum\limits_{i=0}^{\lg(n)-1} \theta(\frac{n}{2^i}) = \theta(n\lg(n))$. Is this incorrect? $\endgroup$
    – user30362
    Apr 6 '15 at 13:18
  • 3
    $\begingroup$ It is $$\sum_{i=0}^{\lg n} 2^i (\frac{n}{2^i}) = \Theta(n \lg n)$$. For details, see this lecture note Page 2. $\endgroup$
    – hengxin
    Apr 6 '15 at 13:24
  • $\begingroup$ See here for some thoughts on your first expression. (Though that's not the issue here.) $\endgroup$
    – Raphael
    Apr 7 '15 at 7:27

Your Answer

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

Browse other questions tagged or ask your own question.