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$
