Complexity question on Python 3 lists

Steven D'Aprano steve+comp.lang.python at
Wed Feb 15 19:41:42 EST 2012

On Wed, 15 Feb 2012 19:20:21 +0100, Franck Ditter wrote:

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


More information about the Python-list mailing list