Optimal resizable arrays

Robert E. Tarjan, Uri Zwick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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(N1/r) space is sufficient for storing and accessing an array of size N, if N + O(N1−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(N1/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.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
EditorsTelikepalli Kavitha, Kurt Mehlhorn
PublisherSociety for Industrial and Applied Mathematics Publications
Pages285-304
Number of pages20
ISBN (Electronic)9781611977585
StatePublished - 2023
Externally publishedYes
Event2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023 - Florence, Italy
Duration: Jan 23 2023Jan 25 2023

Publication series

NameProceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023

Conference

Conference2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
Country/TerritoryItaly
CityFlorence
Period1/23/231/25/23

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Optimal resizable arrays'. Together they form a unique fingerprint.

Cite this