efficient idiomatic queue?

David Eppstein 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 mailing list