Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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) $$
to:
$$ 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$?
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.
