1
$\begingroup$

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\,?$$

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Feb 4 '18 at 17:31
  • $\begingroup$ 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. $\endgroup$ – Raphael Feb 4 '18 at 17:32
1
$\begingroup$

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

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