Amortized Analysis

Feedback

The strategy for arbitrary inserting and removing sequence is incorrect. Consider the following scenario: The current size of the array is and it contains elements. Now, I remove the last element. According to your algorithm, the array shrinks and costs time. Now the array is of length and has elements. Then I insert two elements to the end. You have to double the length of the array again, costing another time. Then I keep removing two elements, inserting two elements, … Your strategy takes time every two operations.

1) inserting

We assume that inserting and copying elements between arrays takes time.

We will choose , doubling the array size every time the array is full.

Now, when there is space in the array, insertion takes time. When the array is full, however, it grows from to elements and requires copying elements.

e.g. when we start with an array of size , the array doubles

This is a geometric series, and the copy costs are

Thus, the copying of elements takes time and the insertion of elements takes amortized time, which translates to

amortized constant time per insertion.


2) removing

We assume that removing elements also takes time.

We can choose to halve the size of the array (which still has length) every time the number of elements frops below of the array’s size.

Suppose we start with an array of size , and the number of elements falls from to . In this case, we shrink the array and copy elements to the new array.

Thus, we come to a total number of copy operations of

Equivalent to the argumentation for copying and inserting elements, copying and removing elements also takes amortized time, i.e. constant time per element.

inserting + removing Since inserting and element takes and deleting also takes , inserting + removing also takes amortized constant time.


informal first draft:

a) Since we also also did it like this in the exercise lesson, I’ve chosen to double the array each time it is resized. Therefore

costs:

  • insertion:
  • insertion with resizing (happens every time):
    1. resizing the array from to takes time
    2. inserting the new element takes time
    3. total:

Therefore, for inserting elements:


b) Shrinking We could shrink a vector when more than half of it is empty.

costs:

  • deletion:
  • deletion with resizing (happens every time):
    1. resizing the array from to takes time
    2. deleting the element takes time
    3. total:

Therefore, for removing elements:

And insertion and deletion together take