2026-07-23T10:10:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8252 2024-03-06T10:41:51Z ddc:004 open_access

On-the-Fly Array Initialization in Less Space Hagerup, Torben Kammer, Frank data structures space efficiency constant-time initialization on-the-fly initialization arrays We show that for all given n,t,w in {1,2,...} with n<2^w, an array of n entries of w bits each can be represented on a word RAM with a word length of w bits in at most nw+ceil(n(t/(2 w))^t) bits of uninitialized memory to support constant-time initialization of the whole array and O(t)-time reading and writing of individual array entries. At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with nw+ceil(n/w^t) bits for arbitrary fixed t, to be compared with nw+Theta(n) bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support O(log n)-time access with just nw+1 bits, which is optimal for arbitrary access times if the initialization executes fewer than n steps. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Torben Hagerup and Frank Kammer 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.44 urn:nbn:de:0030-drops-82527 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.44 eng https://creativecommons.org/licenses/by/3.0/legalcode