# Amortized analysis for doubling resizing array is ~3n

I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused:

Question 2: What if instead we decide to double the size of the array when we resize?

Answer 2: This is much better. Now, in any sequence of n operations, the total cost for resizing is $1 + 2 + 4 + 8 +. . .+ 2^i$ for some $2^i < n$ (if all operations are pushes then $2^i$ will be the largest power of $2$ less than $n$). This sum is at most $2n−1$. Adding in the additional cost of $n$ for inserting/removing, we get a total cost $<3n$, and so our amortized cost per operation is $< 3$.

How did we arrive at $2n-1$?

I know that the sum of powers of $2$ is $2^{n-1}-2$, but does that matter at all here? I know that $2^{n-1} -2$ is very different from $2n-1$, but I'm not seeing how you can get $2n-1$ from the sum of $1 + 2 + \dots +2^i$ where $2^i$ is largest power of $2$ before $n$ item.

If anyone can give concrete examples, that would be great because that's how I understand better.

I know where the remaining $n$ comes from which makes this whole operation $3n$.

• Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour, if you have not yet done so. – babou Aug 8 '15 at 8:49

Note that the statement involves two variables $i$ and $n$. The sum of powers of two equals the next power minus one: $\sum_{k=0}^i 2^k = 2^{i+1}-1$. It is mentioned that $2^i$ is the largest power less than $n$. That means $2^i < n \le 2^{i+1}$.
As $2^i < n$ we have that the sum $2\cdot 2^i -1$ is less than $2n-1$.