Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

MIT Lecture Slide

share|improve this question
    
It, the summation, is actually in $\mathcal O(1)$, as you have a closed form, which is $2n-1$, which can be evaluated directly. –  Pedro Nov 4 '12 at 17:33
    
@Pedro They don't investigate the cost of computing the sum, but the asymptotic growth of the sum itself. –  Raphael Nov 5 '12 at 16:55
    
@Raphael: Yes, that is quite obvious, but the question refers to how the sum suddenly becomes $2n$. –  Pedro Nov 5 '12 at 17:08
    
@Pedro Nowhere in the question does $2n$ occur. –  Raphael Nov 5 '12 at 17:14
    
@Raphael: Are you having a bad day? When the poster says "I feel that the summation he does is wrong", it is quite obvious he is referring to the fact that he doesn't understand the math. That this has nothing to do with the answer being in $\Theta(n)$, is also quite obvious. I was pointing out that his question is not exactly well formulated, i.e. that the sum itself had nothing to do with the $\Theta(n)$. –  Pedro Nov 5 '12 at 18:19
add comment

1 Answer

up vote 4 down vote accepted

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$.

share|improve this answer
    
ohh yes you are right, sorry I was summing it to n. Thanks :D –  user1675999 Nov 4 '12 at 18:57
1  
You can also see this by looking at the binary representation. The sum is represented by 111111111... with $k+1$ 1s. Obviously, 111111111 = 1000000000 - 1, where there are $k+1$ 0s in the number. –  SamM Nov 5 '12 at 1:03
    
How do guy know all this, we started off learning algorithms without having a foundation on discreet math :/ –  user1675999 Nov 5 '12 at 4:53
    
@user1675999 Poor you. For what it's worth, the TCS Cheat Sheet can be a useful reference for formulae. –  Raphael Nov 5 '12 at 8:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.