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

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.

-
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

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

-
ohh yes you are right, sorry I was summing it to n. Thanks :D – user1675999 Nov 4 '12 at 18:57
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