On 11/7/2009 5:18 PM Carl Banks said...
I think the top one is O(N log N), and I'm suspicious that it's even
possible to grow a list in less than O(N log N) time without knowing
the final size in advance. Citation?
Quoting Tim --
Python uses mildly exponential over-allocation, sufficient so
that growing a list takes *amortized* O(1) time per append.
Speed of indexed list access is much more important in most
apps than speed of append, but Python has good O() behavior
for both. O() behavior for deleting (or inserting) "in the
middle" of a list is atrocious, though (O(len(list)). Life
is a never-ending sequence of tradeoffs <wink>.
--
For full context see
http://groups.google.com/g/2e77fef2/t/82ee7a80757e84ab/d/6d1c154901794bb
Emile
--
http://mail.python.org/mailman/listinfo/python-list
