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

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?

• 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. Apr 6 '15 at 13:13
• 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? Apr 6 '15 at 13:18
• 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. Apr 6 '15 at 13:24
• See here for some thoughts on your first expression. (Though that's not the issue here.)
– Raphael
Apr 7 '15 at 7:27