On-the-Fly Array Initialization in Less Space

Torben Hagerup, Frank Kammer

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…