# Complexity question on Python 3 lists

F

#### Franck Ditter

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.
Do lists in Python 3 behave like ArrayList in Java (if the capacity
is full, then the array grows by more than 1 element) ?

def sdiv(n) : # n >= 2
"""returns the smallest (prime) divisor of n"""
if n % 2 == 0 : return 2
for d in range(3,int(sqrt(n))+1,2) :
if n % d == 0 : return d
return n

def isPrime(n) :
"""Returns True iff n is prime"""
return n >= 2 and n == sdiv(n)

def primes(n) : # n >= 2
"""Returns the list of primes in [2,n]"""
res = []
for k in range(2,n+1) :
if isPrime(k) : res.append(k) # cost O(1) ?
return res

Thanks,

franck

C

#### Chris Rebert

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.
Do lists in Python 3 behave like ArrayList in Java (if the capacity
is full, then the array grows by more than 1 element) ?

Yes. Python lists aren't linked lists. list.append() resizes the
underlying array intelligently to give O(1) performance, although I
can't find any guarantee of this in the docs, but it is true in
practice for all major Python implementations.

Cheers,
Chris

I

#### Ian Kelly

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

D

#### Dave Angel

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.
Do lists in Python 3 behave like ArrayList in Java (if the capacity
is full, then the array grows by more than 1 element) ?

def sdiv(n) : # n>= 2
"""returns the smallest (prime) divisor of n"""
if n % 2 == 0 : return 2
for d in range(3,int(sqrt(n))+1,2) :
if n % d == 0 : return d
return n

def isPrime(n) :
"""Returns True iff n is prime"""
return n>= 2 and n == sdiv(n)

def primes(n) : # n>= 2
"""Returns the list of primes in [2,n]"""
res = []
for k in range(2,n+1) :
if isPrime(k) : res.append(k) # cost O(1) ?
return res

Thanks,

franck
Yes, lists behave the way you'd expect (see vector in C++), where when
they have to reallocate they do so exponentially.

However, realize that your algorithm is inefficient by a huge factor
more than any time spent expanding lists. The biggest single thing you
need to do is to memoize -- store the list of known primes, and add to
it as you encounter more. Then use that list instead of range(3, xxx,
2) for doing the trial divisions.

S

#### Stefan Behnel

Ian Kelly, 15.02.2012 19:43:
I believe the behavior in CPython is that if the array is full, the
capacity is doubled

But only up to a certain limit. After that, it grows in constant steps.
Otherwise, your memory would be bound to explode on an append even though
your list uses only half of it (or one third, in case it needs to copy).

, but I'm not certain, and that would be an
implementation detail in any case.

Absolutely.

Stefan

D

#### Dennis Lee Bieber

"The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …"
-- list_resize()
Rather perverse, is it not? The first set is plain doubling, but
then you get a series of increases by:

... 9, 10, 11, 12, 14, 16, 16,...

or

100%, 100%, 100%, 56%, 40%, 34%, 30%, 27%, 22%,...

Big jump form 100% to 56%...

I

#### Ian Kelly

Rather perverse, is it not? The first set is plain doubling, but
then you get a series of increases by:

... 9, 10, 11, 12, 14, 16, 16,...

or

100%, 100%, 100%, 56%, 40%, 34%, 30%, 27%, 22%,...

Big jump form 100% to 56%...

Based on the formula in the code, it would seem to asymptotically
approach 12.5%.

S

#### Steven D'Aprano

What is the cost of calling primes(n) below ? I'm mainly interested in
knowing if the call to append is O(1)

Your primes() function appears to be a variation on trial division, which
is asymptotically O(n*sqrt(n)/(log n)**2). Regardless of the exact Big Oh
behaviour, it is going to be SLOW for large values of n.

The behaviour of append is the least of your concerns.

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.