Arrays/Python/DynamicArrayResizing

Dynamic array resizing:

Review of question 5-16

Question C-5.16 states: Implement a pop method for the DynamicArray class (link: Arrays/Python/DynamicArray) that removes the last element of the array, and that shrinks the capacity C of the array in half any time the number of elements in the array goes down by C/4.

Here is the implementation for this problem:

    def pop(self):
        """Pop obj from end of array"""
        self._A[self._n] = None
        self._n -= 1
        if(self._n < self._capacity//4):
            self._resize(self._capacity//2)

This pop method changes the capacity by cutting it in half, not in quarters, thus forcing extra room at the end of the array. By maintaining this extra space that is proportional to n, the O(n) cost of appending or popping is amortized over O(n) operations that are O(1) each.

Question 5-19 - Resizing capacity if n drops below one quarter capacity

This asks pop method implemented for 5-16 looks like this:

    def pop(self):
        """Pop obj from end of array"""
        self._A[self._n] = None
        self._n -= 1
        if(self._n < self._capacity//4):
            self._resize(self._n)

The cost of performing any sequence of n push or pop operations will be O(n). That's because the worst case is 2 O(n) operations in a row - one O(n) operation to shrink the capacity of the array to size n, then a consecutive append operation that requires another O(n) operations, for 2n total operations. This is still just O(n) overall. The O(n) shrink operation can be amortized over at least (3/4)n operations, if we keep popping elements, or the O(2n) shrink-then-expand operation can be amortized over at least n append operations.

Question 5-20 - Resizing capacity if n drops below one half capacity

If we are not careful about how we store list, we may force a combination of capacity resizing that can be toggled back and forth with a single operation, thus wiping out any amortization.

For example, if we double the capacity of an array when its capacity is exceeded by 1, and we then halve the capacity of an array when its capacity is reduced to less than half, we can induce an O(n) cost with a single operation, adding to a 100% full array and forcing an O(n) resize. Then we can induce another O(n) cost with a single operation, removing one item from a now 50% full array. The O(n) cost is not amortized over n operations. Thus we can assemble a sequence of n operations with an O(n) cost.