Let V be a dynamic array of n elements stored in a buffer of capacity c, with the…

Let \(V\) be a dynamic array of \(n\) elements stored in a buffer of capacity \(c\), with the invariant \(0 \le n \le c\) and \(c \ge 1\). The operation \(\mathrm{Append}\) writes a new element in time \(\Theta(1)\) if \(n < c\). If \(n = c\), \(\mathrm{Append}\) allocates a new buffer of capacity \(2c\), copies the \(n\) existing elements, writes the new element, and deallocates the old buffer. The operation \(\mathrm{Truncate}\) removes the last element in time \(\Theta(1)\) if \(n > 0\) and, after the removal, if \(n \le \lfloor c/4 \rfloor\) and \(c \ge 2\), it allocates a new buffer of capacity \(\lfloor c/2 \rfloor\), copies the remaining \(n\) elements, and deallocates the old buffer. Adopt the standard uniform-cost RAM model in which allocating or deallocating a buffer of capacity \(k\) and copying \(k\) elements each cost \(\Theta(k)\), and all other primitive steps cost \(\Theta(1)\). Starting from \(n = 0\), \(c = 1\), consider an arbitrary mixed sequence of \(m\) successful \(\mathrm{Append}\) and \(\mathrm{Truncate}\) operations (\(\mathrm{Truncate}\) is never invoked on an empty array). Prove that the amortized cost of each operation is \(O(1)\). You may use either the aggregate method or the accounting method; if you use accounting, state the credit invariant relating stored credits to \(n\) and \(c\), and prove that the invariant is maintained and that every operation's actual cost is covered. Finally, exhibit a concrete infinite family of operation sequences showing that if shrinking were instead triggered whenever \(n \le \lfloor c/2 \rfloor\) after \(\mathrm{Truncate}\) (with new capacity \(\lfloor c/2 \rfloor\)), then the amortized cost would no longer be \(O(1)\).

The shrink threshold, rather than the grow threshold, is what stops a single Truncate after a doubling from immediately reallocating.