1
$\begingroup$

I am curious on the use of the potential method for amortized analysis for a dynamic array which quadruples in size after it becomes full.

I understand how the potential function is defined and used for such an array which doubles in size, but am having difficulty showing that the insert operation takes constant time in the case of the 4x array.

Here's what I have so far, any insight or hints would be greatly appreciated! If there are any formatting errors in my question, please let me know and I'll try to fix them.

Let $\Phi(A_{i}) = 4n_{i} - s_{i}$, where $n_{i}$ is the amount of elements in the array after the ith insertion, and $s_{i}$ is the total capacity of the array.

When no allocation of a new array is needed, so no elements need to be copied and only the inserting is performed:

\begin{align*} \hat{c_{i}} &= c_{i} + \Phi(A_{i}) - \Phi(A_{i-1})\\ &= 1 +(4n_{i}-s_{i}) - (4n_{i-1}-s_{i-1})\\ &= 1+(4(n_{i-1}+1)-s_{i-1})-4n_{i-1}+s_{i-1}\\ &= 5. \end{align*}

When $n_{i-1}=s_{i-1}$, so a new array of size $s_{i} = 4s_{i-1}$ must be allocated, with all elements in the previous array copied over plus the new element:

\begin{align*} \hat{c_{i}} &= c_{i} + \Phi(A_{i}) - \Phi(A_{i-1})\\ &= n_{i} + (4n_{i}-s_{i})-(4n_{i-1}-s_{i-1})\\ &= n_{i-1}+1+(4(n_{i-1}+1)-4n_{i-1})-(4n_{i-1}-n_{i-1})\\ &= n_{i-1}+1+(4n_{i-1}+4-4n_{i-1})-3n_{i-1}\\ &= n_{i-1}+1+4-3n_{i-1}\\ &= -2n_{i-1}+5. \end{align*}

I'm uncertain how to proceed at this point. I have been experimenting with different potential functions but this one seems intuitive, as $n \geq \frac{s}{4}$.

$\endgroup$
1
  • $\begingroup$ I'm not sure I see the problem. You have shown that the amortized cost of each operation is at most 5. $\endgroup$ Feb 8, 2021 at 12:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.