Pergunta

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

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top