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
0 comments:
Post a Comment
Let us know your responses and feedback