Dynamic Arrays and Amortized Analysis >> Data Structures
*Please Do Not Click On The Options.
* If You Click Mistakenly Then Please Refresh The Page To Get The Right Answers.
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 nn 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 \leq≤ 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 nn PushBack and PopBack operations, starting with an empty dynamic array.
What potential function would work best to show an amortized O(1)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)O(1) since the true cost of each operation is O(1)O(1).
What is the amortized cost of any operation in a sequence of nn stack operations (starting with an empty stack) that includes PopMany (choose the best answers)?