Technical question on complexity.

[Fredrik Lundh]

Jerzy Karczmarczuk wrote:

> Anybody knows where I can find a concrete and guaranteed answer to the following
> extremely basic and simple question?
>
> What is the complexity of appending an element at the end of a list?

amortized O(1)

> Concatenating with another?

O(n)

> The point is that I don't know what is the allocation policy... If Python lists
> are standard pointer-chained small chunks, then obviously linear. But perhaps
> there is some optimisation, after all a tuple uses a contiguous chunk, so it
> *might* be possible that a list is essentially equivalent to an array, with its
> length stored within, and adding something may be done in constant time

a list consists of a single array of PyObject pointers, plus "allocated" and
"current size" fields.  when you append, allocation is only done when needed,
and the new size is chosen carefully to keep the number of allocations low.
see the source for details (the exact "overallocation" strategy varies some-
what in different Python versions).

</F>