We don't bite newbies here... much | |
PerlMonks |
Re: Data structure challenge (amortized)by Abigail-II (Bishop) |
on Mar 18, 2004 at 00:15 UTC ( [id://337565]=note: print w/replies, xml ) | Need Help?? |
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
In Section
Meditations
|
|