How to compute amoritized cost for a dynamic array?

Question

I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method.

Let A of size m be an array of n elements. When $n = m$, then we create a new array of size $4m$, and then copy the elements of A to the new array. When $n = \frac{m}{4}$, then you create a new array of size $\frac{m}{4}$, and copy the elements to that array.

What I am confused about is how to calculate the costs. From what I know so far: Before the first expansion, you pay two dollars to insert. 1$ for the insert, and 1$ you just store with the element, so that you can use that later for a copy operation.

Then when you expand it, you use that stored $ to move the element to the new array. Now in the new array the elements won't have any $ with them. But now as you insert a new element, you use 3$. 1$ for the insert, then one more for itself (for a future copy), and one more for the previous element that was just copied.

The problem here is, what if you have an array like this:

1$ 2$

Then insert an element

1$ 2 3$ _ _ _ _ _

Now how do you handle a delete operation?

Answer 1

I think your particular structure does not have amortized $O(1)$ cost, and you identified the problem.

Your general approach is salvageable, but you either need to grow less aggressively or shrink less aggressively. The standard solution is to grow from capacity & size $n$ to capacity $2n$ and to shrink from capacity $n$ and size $n/4$ to capacity $n/2$.