How can I have constant time initialization for multi-dimensional arrays?
It is amortized constant time, independent of the number of elements eventually used (initialized). But going to that complexity might just not be worth the time saved (if any).

A more practical way (due to Kernighan and Pike, IIRC) is to allocate an initial number of elements for a linear array, if you run out reallocate twice the number and initialize the new elements. The amortized cost is again constant for each initialized element, with less hassle. This obviosly works only for the case in which elements are added (mostly) sequentially; but if the elements are allocated haphazardly you'll probably be better off with another type of structure, like a hash table or some sort of tree.