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 ?
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 ?
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} $