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 -