Complexity question on Python 3 lists

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.

-- 
Steven