As long as we're only talking big-O notation, I think that that O(n) initialization is a wash. Inserting n items at O(1) is O(n). And O(n) (for initialization) + O(n) (for n insertions) = O(n).
Comment on Re^4: Data structure challenge (amortized)
I'm not sure what you mean. Note that if you use an array,
the array size is U. And, yes, n insertions,
each taking constant time is O (n). However, initializing all elements of an array of size U
takes Θ (U). But it's not given that
U = O (n). There might only be O (sqrt (U))
insertions.