We have an array that supports both insert and remove operations. This is an extendable$-$

shrinkable array that does the following, where N is the current capacity of the array:

when there are N elements and we insert one more, the array is extended so the new

capacity is $2$ N

when we remove an element so the number of elements dips below N$/4,$ we shrink the

array so the new capacity is $\frac{N}{2}$

a$)$ Show that a sequence of n insert and remove operations, starting from an extendable$-$

shrinkable array of capacity $N=1,$ takes $O(n)$ time. Use the accounting method, but be very

clear about what is getting "paid forward" towards what.

b$)$ What can you conclude about the amortized time of the insert and remove operations for this

extendable$-$shrinkable array?