The Algorithm Design Manual (3rd) Exercise Solution 'E3-5'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-5

Question

We have seen how dynamic arrays enable arrays to grow while still achieving constant-time amortized performance. This problem concerns extending dynamic arrays to let them both grow and shrink on demand.

(a) Consider an underflow strategy that cuts the array size in half whenever the array falls below half full. Give an example sequence of insertions and deletions where this strategy gives a bad amortized cost.

(b) Then, give a better underflow strategy than that suggested above, one that achieves constant amortized cost per deletion.

Solution

Solution For Subproblem (a)

The worst case is when an event where the array shrinks and that where the array expands occur alternately, and the amortized performance falls into $O(n)$.

For example, suppose, now array size is 64 with spaces in 0-32 indices filled.

Define two steps of operation below.
(step-1) Delete the last item of array, which causes the array to shrink to 32 size.
(step-2) Insert a item to array, which conversely causes the array to expand to 64 size again.

Iterating step-1 and step-2, the array size vibrates and performance is very inefficient.

Solution For Subproblem (b)

Instead of the "half" timing strategy, we can cut the array size in half whenever the array falls below "quarter" full, which keep the array from vibrating its size and performance goes up to $O(1)$