1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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, 2015 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, 2015 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, 2015 at 13:24
  • $\begingroup$ See here for some thoughts on your first expression. (Though that's not the issue here.) $\endgroup$
    – Raphael
    Apr 7, 2015 at 7:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.