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 element1$ 2 3$ _ _ _ _ _Now how do you handle a delete operation?
How to compute amoritized cost for a dynamic array?
data structures;algorithm analysis;amortized analysis