Complexity question on Python 3 lists

[Chris Rebert]

On Wed, Feb 15, 2012 at 10:43 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
> On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter <franck at ditter.org> wrote:
<snip>
>> Do lists in Python 3 behave like ArrayList in Java (if the capacity
>> is full, then the array grows by more than 1 element) ?
>
> I believe the behavior in CPython is that if the array is full, the
> capacity is doubled, but I'm not certain, and that would be an
> implementation detail in any case.

It's slightly more complex:
http://hg.python.org/cpython/file/096b31e0f8ea/Objects/listobject.c
"The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …"
    -- list_resize()

Cheers,
Chris