1
$\begingroup$

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

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

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

I am a little confused as the text states "at most" rather than "less than".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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