[Solved]: Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$?

Problem Detail: 

I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09).

Although you guys don't have to go and look at the video, I feel that the summation he does is wrong so I will attach the screenshot of the slide.

Asked By : user1675999

Answered By : A.Schulz

If you have a series of numbers that are consecutive power of 2s, like $1+2+4+8+16+\cdots+2^k$ you get as sum $2^{k+1}-1$. You can either see this by looking at the formula for the geometric series or you can prove this by induction.

Then the statement of the lectures follows, since here $k=\lfloor \log (n-1) \rfloor$. Therefore the sum is less than $2n$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6473

3.2K people like this

 Download Related Notes/Documents