Complexity question on Python 3 lists
Steven D'Aprano
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.
--
Steven
More information about the Python-list
mailing list