Consider a dynamic array data structure consisting of an array with initial size 1, together with a ...

---

Consider a dynamic array data structure consisting of an array with initial size 1, together with a variable "size" denoting the number of slots that currently contain data. Insert() and Delete() are supported. Insert() inserts an element into the first empty slot in the array, while Delete() deletes the element in the last occupied slot. To make the structure adaptable in size, Expansion() and Shrink() are triggered by Insert() and Delete() respectively. If after Insert() the array is full, a new array with double the size is created and the contents of the old array are copied to the new array one by one. If after Delete() less than 1/4 of the slots are occupied, a new array with half the size is created and the contents are copied over (no shrinking is done if the array has size 2). (a) What is the worst-case running time of Insert() if the array size is n? (b) What is the amortized running time of a sequence of n Insert() and Delete() operations? (c) Give a proof of the amortized running time in part (b).