Complexity question on Python 3 lists
steve+comp.lang.python at pearwood.info
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