Problem 2: Consider a variation of the extensible array data structure that we learned about in class. As before it gets full. For the in-class version, when we doubled the array, allocating new memory was free, but we had to pay $1 per element to copy each of the elements already in the array to the new location. Now, suppose we have to also pay to allocate new memory, and this costs $1 per unit of space that we allocate. For example, if the array currently has size k and we need to double it, then we would pay a total of S3k to create the new, larger array: $2k to allocate 2k units of space, and Sk to copy over all the existing elements. , we double the size of the array whenever Consider a sequence of n insertions into this array. What is an upper bound on the average length of time that an insertion can take? Report your answer in units of time (or dollars), not big-O notation