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 = m/4, then you create a new array of size 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
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:
Then insert an element
1$ 2 3$ _ _ _ _ _
Now how do you handle a delete operation?