Amortized Analysis of Dynamic Arrays: The Mathematical Bounds of Array Appending

AMORTIZED ANALYSIS OF DYNAMIC ARRAYS: THE MATHEMATICAL BOUNDS OF ARRAY APPENDING A standard array has a fixed size allocated at creation. A dynamic array (such as list in Python or vector in C++) allows appending elements dynamically. When the array is full, appending requires allocating a new, larger array and copying all elements. While a single resize operation is slow, we prove using Amortized Analysis that the average cost of an append operation remains O(1) constant time. THE REALLOCATION COST MODEL Suppose a dynamic array doubles its size when full, starting with a capacity of 1. If we append N elements: - Most appends cost 1 operation (writing the value). - If the capacity is exceeded (at N = 1, 2, 4, 8, 16...), we must copy all existing elements to the new block. AGGREGATE METHOD PROOF Let's calculate the total cost of N append operations where N is a power of 2. Total cost = (Cost of N writes) + (Cost of copying elements during resizes) Total cost = N + (1 + 2 + 4 + 8 + ... + N/2) The summation of the geometric series (1 + 2 + 4 + ... + N/2) is equal to N - 1. Total cost = N + (N - 1) = 2N - 1. To find the average (amortized) cost per operation, we divide the total cost by N: Amortized cost = (2N - 1) / N = 2 - (1/N) < 2. Because the amortized cost is bounded by a constant (2), the append operation has an amortized time complexity of O(1). POTENTIAL FUNCTION ANALYSIS We can also prove this using the Physicist's Method by defining a potential function, Phi, representing the "stored energy" in the array. Let the potential function be: Phi = 2 * Size - Capacity At a resize boundary (Size = Capacity), the potential energy is equal to the capacity, which perfectly offsets the cost of copying all elements. This potential analysis guarantees that the amortized complexity remains constant under any sequence of appends. Reference: Yang Hu, "Algorithms Python.pdf", Chapters 6 & 7: Linear Table Append & Insert.