TY - GEN

T1 - Optimal resizable arrays

AU - Tarjan, Robert E.

AU - Zwick, Uri

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85193375360&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85193375360&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85193375360

T3 - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023

SP - 285

EP - 304

BT - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023

A2 - Kavitha, Telikepalli

A2 - Mehlhorn, Kurt

PB - Society for Industrial and Applied Mathematics Publications

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

Y2 - 23 January 2023 through 25 January 2023

ER -