One approach to implementing an array-based list where the list size is unknown is to let the array grow and shrink. This is known as a dynamic array.

When necessary, we can grow or shrink the array by copying the array’s contents to a new array. If we are careful about the size of the new array, this copy operation can be done rarely enough so as not to affect the amortized cost of the operations.

(a) What is the amortized cost of inserting elements into the list if the array is initially of size 1 and we double the array size whenever the number of elements that we wish to store exceeds the size of the array? Assume that the insert itself cost O(1) time per operation and so we are just concerned with minimizing the copy time to the new array.

(b) Consider an underflow strategy that cuts the array size in half whenever the array falls below half full. Give an example where this strategy leads to a bad amortized cost. Again, we are only interested in measuring the time of the array copy operations.

(c) Give a better underflow strategy than that suggested in part (b). Your goal is to find a strategy whose amortized analysis shows that array copy requires O(n) time for a series of n operations.