# 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. Aug 8, 2015 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$.