Surprising (for me) benchmark results...

[Daniel Berlin]

On Wed, 2 May 2001, Courageous wrote:

>
> >If you want to consider things that way then you have to worry
> >about Python's list extension, which last I heard was O(N**2)...
>
> NO.
>
> list.append() appends items to a dynamic array in O(1)+k
> constant amortized time. It does this by using a liberal preallocation
> strategy, and leaving empty slots into which new elements can
> be placed. The occasional realloc() amortizes away quite readily.

Are you sure?
You also have to amortize the sliding of the elements, not just the
resizing.
This is possibly O(n).
This is in ins1, in listobject.c, It does this right after the resize.
It's  pretty clear that it may have to slide all but one item, which would
be another O(n) to amortize away. Unless this is the k, in which case
k can be n-1 worst case, making it pretty pointless to claim it's
O(1).