Re: Re^2: Data structure challenge (amortized)

I'm not allowed to amortize the initialization over the life of the structure: but what about over the life of the program: is it valid (in the context of this challenge) big array (vec, whatever) at time zero and then manage it using my own allocator?

Comment on Re: Re^2: Data structure challenge (amortized)

Replies are listed 'Best First'.
Re^4: Data structure challenge (amortized) by sleepingsquirrel (Chaplain) on Mar 18, 2004 at 00:01 UTC
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).	[reply]
Re: Data structure challenge (amortized) by Abigail-II (Bishop) on Mar 18, 2004 at 00:15 UTC
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	[reply]