efficient idiomatic queue?
eppstein at ics.uci.edu
Tue Jan 15 17:05:05 CET 2002
In article <7xr8osorq1.fsf at ruckus.brouhaha.com>,
Paul Rubin <phr-n2002a at nightsong.com> wrote:
> "Alex Martelli" <aleax at aleax.it> writes:
> > I think this should be constant-amortized-time,
> I think logarithmetic amortized time, i.e. calling pop N times takes
> O(N log N) time (because it has to do a linear-time operation every so often).
No, Alex was right, it is constant amortized time.
Each linear time operation (reducing the list length)
can be charged against the insertion operations that added the items being
removed from the list.
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/
More information about the Python-list