# What is the value of this summation in Big O terms?

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 ?

-
did you mean to have the exponent of $2$ different than the index of summation? –  robjohn Sep 7 '12 at 10:30
@robjohn it was a typo.fixed it . thnanks for pointing this. –  Geek Sep 7 '12 at 10:31

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}