I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there).

Here is what I am reading from. (starts at pg. 30) This example has the array doubling when it is filled.

This is my potential function analysis so far: But in the end I am getting 7-2i, I don't think it can be like that. I think the i's should cancel out.

Does anyone know whats wrong?

Potential of the array after the $i^{th}$ insertion is $\Phi(D_i) = 4i - 4^{\left\lceil \log_{4}i\right\rceil}$.

Assume $4^{\left\lceil \log_{4}0\right\rceil} = 0$.

The amortized cost of the $i^{th}$ insertion is:

$\^c_i = c_i + \Phi(D_i)-\Phi(D_{i-1})$

$~~~= \{ i$ if $i-1$ is an exact power of $4$

$~~~~~~~\{ 1$ otherwise

$~~~~~~~+ (4i-4^{\left\lceil \log_{4}i\right\rceil})-(4(i-1)-4^{\left\lceil \log_{4} (i-1)\right\rceil})$

$~~~= \{ i$ if $i-1$ is an exact power of $4$

$~~~~~~~\{ 1$ otherwise

$~~~~~~~+ 4-4^{\left\lceil \log_{4}i\right\rceil}+4^{\left\lceil \log_{4}(i-1)\right\rceil}$

Case 1 ($i-1$ is an exact power of $4$):

$\^c_i = i + 4-4^{\left\lceil \log_{4}i\right\rceil}+4^{\left\lceil \log_{4}(i-1)\right\rceil}$

$~~~= i + 4-4(i-1)+(i-1)$

$~~~= i + 4-4i+4+i-1$

$~~~= 7-2i$

  • $\begingroup$ Please, edit your earlier posts! $\endgroup$
    – Raphael
    Mar 12, 2013 at 10:24