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, and leaving empty slots into which new elements can
>> be placed. The occasional realloc() amortizes away quite readily.

>Are you sure?

Yes.

>You also have to amortize the sliding of the elements, not just the
>resizing. This is possibly O(n).

I was talking about append-at-the-tail, which is what listobject
append does. See the reference manual for python. There is no
positional argument; list.append() uses the insert at end special
condition of ins1.

>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).

No, we're just talking past each other. Traditional list
operations where you insert in the middle are called "insert",
which is what you're thinking of, which is, indeed, O(n).

If we weren't supposed to be talking about list.append(),
sorry. :-)

C//