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 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?
There are no amortized costs for an array like this.
Consider your example 1$ 2$. When adding one element, you will have to increase the size of the array. Now remove one element, and you have to reduce the size. Now again add one element. Etc.
Now consider a larger array with n = m. By increasing n, it gets more and more expensive to add and remove one single element. In fact, you can make the cost for adding and removing one single element arbitrarily high, and thus, there cannot be amortized costs.