4
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is a pretty standard trick, which follows by combining two interpretations of the double condition $1 \leq k \leq h \leq m$. Now that you've seen it, you can apply it yourself in other situations (with other double or multiple conditions). $\endgroup$ – Yuval Filmus Sep 20 '16 at 1:49
2
$\begingroup$

Exponentials grow very fast — your very first guess should be that the sum is asymptotically on the order of its final term.

In fact, it's easy to get actual bounds here. It's should be familiar result that $2^m$ is larger than $\sum_{k=0}^{m-1} 2^h$ (but if not, it's a geometric series), and so $m 2^m$ is larger than $\sum_{h=0}^{m-1} m 2^h$ which is larger than $\sum_{h=0}^{m-1} h 2^h$. Thus,

$$ m 2^m < \sum_{h=0}^m h 2^h < 2 m 2^m $$

with $m = \lfloor \lg n \rfloor$, it's now esay to see the sum is $\Theta(n \lg n)$.

If you care about the overall constant, since only the last terms matter and for those $h \sim m$, you should guess $\sum_{k=0}^m h 2^h \sim m \sum_{k=0}^m 2^h \sim 2m 2^m$.

We can establish rigorous lower bounds (or a slightly more precise upper bound) similarly. Taking the last $(k+1)$ terms gives

$$\begin{align} \sum_{h=0}^m h 2^n &> \sum_{h=m-k}^m h 2^h > (m-k) \sum_{h=m-k}^m 2^h \\&= (m-k) (2^{m+1} - 2^{m-k}) \\&= 2m2^m (1 - \frac{k}{m}) (1 - 2^{-(k+1)}) \end{align}$$

$\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.