<h1>It can be Done!</h1>
<p>You can initialize an array in <strong>O(1) worst-time</strong> and O(1) extra space, and it can be improved to using only <strong>1 extra bit</strong> of memory.</p>
<p>Both can be found in this <strong><a href="https://arxiv.org/abs/1709.08900" rel="nofollow noreferrer">Paper</a></strong>,  explained simply in this <strong><a href="https://link.medium.com/Q8YbkDJX2bb" rel="nofollow noreferrer">Article</a></strong>, and implemented in the <strong><a href="https://github.com/tomhea/farray" rel="nofollow noreferrer">Farray</a></strong> project. <br>
Full disclosure - the last two were written by me.</p>
<p>It is the <strong>state-of-the-art</strong> Initializable array, and will <em>probably stay that</em>. The above paper proves that without the extra bit - the fill (init) operation should take Ө(n) time, even for amortized/randomized algorithms.</p>
initializing an n elements array using O(1) performence?
<p>someone has an idea how can I do that ?</p>

<p>thanks</p>