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.

Abigail