Complexity question on Python 3 lists

Steven D'Aprano steve+comp.lang.python at pearwood.info
Thu Feb 16 01:41:42 CET 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.



-- 
Steven



More information about the Python-list mailing list