Consider the extensible array data structure that we learned in class. Suppose there is no extra cost for allocating memory. Suppose that we want to add another operation to this data structure: Remove, which deletes the last element added. In order to make sure that the array doesnt take up too much space, we say that if the array is at least half empty, we will reallocate memory that is only half the size of the current array, and copy all the elements over. This is basically the opposite of the insertion operation from before.

Part a: Does amortized analysis make sense here? In other words, does it allow us to get a tighter bound than the standard analysis?

Part b: Instead of reallocating memory if the array becomes half empty, we reallocate/copy if the array becomes at least 3/4 empty (only 1/4 of the array cells are being used). Analyze the running time of a sequence of n operations using amortized analysis. Hint: this is a straightforward modication of the original extensible array analysis. If we shrink an array, how many elements get added before we next double it? If we are deleting elements, how many do we delete before shrinking it?