I'm in the process of self-studying the CLRS book. My mathematical background is poor so I'm trying to learn the maths as I go along too.

I don't understand the math in CLRS section 6.4 where they go from:

$$ \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} O(h) $$


$$ O\left(n \sum_{h=0}^{\lg n} \frac{h}{2^h}\right). $$

I understand that the $n$ is moved out to before the sum. But how does the remaining $1/2^{h+1}$ become $h/2^h$?

  • 1
    $\begingroup$ You seem to have forget the $O(h)$ factor. This explains where the $h$ comes from. Since $1/2^{h+1}$ and $1/2^h$ differ only by a constant factor, they are interchangeable in big O notation. $\endgroup$ – Yuval Filmus Sep 6 '16 at 1:33
  • $\begingroup$ Just as a tip: the CLRS book is great at making people losing the big intuition about algorithms because if focus too much on math formalism instead of focusing on understanding. If you are having this problem, try the book Algorithms and Data Structures by Robert Lafore. It is unbeatable in terms of pedagogical approach. I can say this from first person experience :) $\endgroup$ – user5193682 Sep 6 '16 at 6:00
  • $\begingroup$ @user9589 YMMV; I think it's often the other way around. $\endgroup$ – Raphael Sep 6 '16 at 8:40
  • $\begingroup$ Your issue is purely with the mathematics of Landau notation; heaps don't come into the picture here at all. $\endgroup$ – Raphael Sep 6 '16 at 8:40

Intuitively, the $O$ can swallow any constant factor. Here, we do so because the sum we get is on the cheat sheet and we can proceed more easily.

Formally, we need to apply the definition of $O$, once in either direction. I do not think the first term makes a whole lot of sense. What the authors probably mean is

$\qquad\displaystyle \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot f(h)$

with some $f \in O(h)$. Then it remains to note that

$\qquad\displaystyle \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot f(h) \quad\leq\quad \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot c \cdot h \quad=\quad \frac{c}{2} \cdot n \cdot \sum_{h=0}^{\lg n} \frac{h}{2^{h}}$

for all $n \geq n_0$, with $c,n_0$ the constants from $f \in O(h)$ (unfold the definition). Applying the definition again concludes the proof.

Note that if we had $f \in \Theta(h)$, we would get a similar lower bound and could thus show a $\Theta$-bound for the sum.


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.