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
    @robjohn it was a t$y$po.$f$ixed 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} $