5
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.