[Solved]: Lower bound of a summation with an exponential

Problem Detail: 

For the following (related to a binary tree complexity question):

$$f(n) = \sum_{h=0}^{\lg{}n} h2^h$$

Is there any way to express this only in terms of $n$? Or approximate it?

---

Put in another way, I figure at worst for an upper bound, we could guess at it in the following way:

$f(n) = 0 + (1 \cdot 2) + (2 \cdot 2^2) + (3 \cdot 2^3) + ... + (\lg{}n \cdot 2^{\lg{}n})$

This means since we go from $0$ to $\lg{}n$, and the largest above when reduced is $n\lg{}n$, I could write $\mathcal{O}(n\lg^2{}n)$.

Supposedly $f(n)$ reduces to $\Theta(n\lg{}n)$ or better (by better I mean closer to $\Theta(1)$) and I'm struggling to show that... and I don't know if it's possible even. I can't prove it though so I can't claim it's not, reducing the summation if possible would hopefully lead to a quick answer.

Asked By : Water

Answered By : Yuval Filmus

There is a general formula for this sum: $$ \sum_{h=0}^m h2^h = \sum_{h=1}^m \sum_{k=1}^h 2^h = \sum_{k=1}^m \sum_{h=k}^m 2^h = \sum_{k=1}^m (2^{m+1}-2^k) = m2^{m+1} - (2^{m+1}-2). $$ Overall, we get $$ \sum_{h=0}^m h2^h = (m-1)2^{m+1} + 2. $$ When $m = \lg n$, this works out to be $2n\lg n - 2n + 2$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63663

3.2K people like this

 Download Related Notes/Documents