Dynamic Arrays and Amortized Analysis

If we have a sequence of 48 operations on an empty dynamic array: 24 PushBack and 24 PopBack (not necessarily in that order), we clearly end with a size of 0.

What are the minimum and maximum possible final capacities given such a sequence of 48 operations on an empty dynamic array? Assume that PushBack doubles the capacity, if necessary, as in lecture.

Give an example of $n$ operations starting from an empty array that require O(n^2)O(n2) copies.

PopBack reallocates the dynamically-allocated array to a new array of half the capacity if the size is $\le$ the capacity / 4 . So, for example, if, before a PopBack the size were 5 and the capacity were 8, then after the PopBack, the size would be 4 and the capacity would be 8. Only after two more PopBack when the size went down to 2 would the capacity go down to 4.

We want to consider the worst-case sequence of any $n$ PushBack and PopBack operations, starting with an empty dynamic array.

What potential function would work best to show an amortized $O(1)$ cost per operation?

Without this new operation, the amortized cost of any operation in a sequence of stack operations (Push, Pop, Top) is $O(1)$ since the true cost of each operation is $O(1)$.

What is the amortized cost of any operation in a sequence of $n$ stack operations (starting with an empty stack) that includes PopMany (choose the best answers)?