2
$\begingroup$

I am trying to do an analysis for the cost of n inserts into a hashtable datastructure and I have a factor like the one below:

$$\sum_{i=0}^{\lfloor\lg {(n-1)}\rfloor} 2^i$$

What will be the Big O of this summation above ?

  • 0
    did you mean to have the exponent of $2$ different than the index of summation?2012-09-07
  • 0
    @robjohn it was a typo.fixed it . thnanks for pointing this.2012-09-07

1 Answers 1

4

Hint: Using the formula for the sum of a geometric series, we get $$ \begin{align} \sum_{i=0}^{\lfloor\lg {(n-1)}\rfloor}2^i &=2^{\lfloor\lg {(n-1)}\rfloor+1}-1\\ &\le2(n-1)+1\\[9pt] &=2n-1 \end{align} $$