Complexity question on Python 3 lists

[Ian Kelly]

On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter <franck at ditter.org> wrote:
> What is the cost of calling primes(n) below ? I'm mainly interested in
> knowing if the call to append is O(1), even amortized.

Yes, it's amortized O(1).  See:

http://wiki.python.org/moin/TimeComplexity

>From a relatively shallow analysis, primes(n) appears to be O(n **
(3/2)), but it might be possible to tighten that up a bit with an
analysis of the distribution of primes and their smallest divisors.

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

Cheers,
Ian