Re^4: Data structure challenge (amortized)

[sleepingsquirrel]

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).

[Abigail-II]

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