Most efficient way to "pre-grow" a list?

[Emile van Sebille]

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