# How to understand the probablistic analysis of skiplist?

I've been studying the skiplist analysis from the open data structures book here: Open Data Structures

I've understood the first 3 lemma's, (after looking at how they use indicator variables in the section 1.3.4 of the book). However, Lemma 4.4 seems pretty vague. Especially, how is $$\sum_{r=1}^{\lfloor\log n\rfloor}1 + \sum_{r=\lfloor\log n\rfloor+1}^\infty n/2^r\leq\log n + \sum_{r=0}^\infty 1/2^r\,?$$

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Feb 4 '18 at 17:31
• Note that this is a pure mathematics question that has little to do with the context in which the inequality appeared. Such questions are better suited for Mathematics. – Raphael Feb 4 '18 at 17:32

The first sum is obviously equal to $\lfloor\log n\rfloor\leq\log n$.
For the second sum, assuming that logs are base-$2$ and using $r>\lfloor\log n\rfloor$,
$$2^r = 2^{\lfloor\log n\rfloor+1}2^{r-\lfloor\log n\rfloor-1} \geq n2^{r-\lfloor\log n\rfloor-1}\,,$$
and the result follows. If the logs aren't base-$2$, then there'll be a scaling factor but the second sum will still be $\Theta(1)$.