Amortized Analysis II

[hamidgasmi]

Let's imagine we add support to our dynamic array for a new operation PopBack (which removes the last element). PopBack will reallocate the dynamically-allocated array if the size is ≤ the capacity / 2 to a new array of half the capacity. 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 4.

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

[hamidgasmi]

Answer:

Let n be a power of 2.
Add n/2 elements, then alternate n/4 times between doing a PushBack of an element and a PopBack.

Explanation:
Once we have added n/2 elements, the dynamically-allocated array is full (size=n/2, capacity=n/2). When we add one element, we resize, and copy n/2 elements (now: size = n/2+1, capacity=n)
When we then remove an element (with PopBack), we reallocate the dynamically allocated array and copy n/2 elements. So, each of the final n/2 operations costs n/2 copies, for a total of n2/4 moves, or O(n^2)