Optimal resizable arrays
share
A resizable array is an array that can grow and shrink by the addition or removal of items from its end, or both its ends, while still supporting constant-time access to each item stored in the array given its index. Since the size of an array, i.e., the number of items in it, varies over time, space-efficient maintenance of a resizable array requires dynamic memory management. A standard doubling technique allows the maintenance of an array of size N using only O(N) space, with O(1) amortized time, or even O(1) worst-case time, per operation. Sitarski and Brodnik et al.describe much better solutions that maintain a resizable array of size N using only N+O(√(N)) space, still with O(1) time per operation. Brodnik et al. give a simple proof that this is best possible. We distinguish between the space needed for storing a resizable array, and accessing its items, and the temporary space that may be needed while growing or shrinking the array. For every integer r≥ 2, we show that N+O(N^1/r) space is sufficient for storing and accessing an array of size N, if N+O(N^1-1/r) space can be used briefly during grow and shrink operations. Accessing an item by index takes O(1) worst-case time while grow and shrink operations take O(r) amortized time. Using an exact analysis of a growth game, we show that for any data structure from a wide class of data structures that uses only N+O(N^1/r) space to store the array, the amortized cost of grow is Ω(r), even if only grow and access operations are allowed. The time for grow and shrink operations cannot be made worst-case, unless r=2.
READ FULL TEXT