Surprising (for me) benchmark results...

[Courageous]

>> list.append() appends items to a dynamic array in O(1)+k
>> constant amortized time. It does this by using a liberal preallocation
>> strategy, ...

>No, it doesn't.

No, it doesn't what?

>See listobject.c:ins1, in particular the line
>
>	NRESIZE(items, PyObject *, self->ob_size+1);

Read the source very carefully. I had to the first time. Although it's
correct to say that it doesn't amortize away to O(1) exactly. It's more
like O(n/500, closing on 1, helped statistically by occasional memory
congruence and other statistical anomalies).

C//