On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter <fra...@ditter.org> wrote: > What is the cost of calling primes(n) below ? I'm mainly interested in > knowing if the call to append is O(1), even amortized.
Yes, it's amortized O(1). See: http://wiki.python.org/moin/TimeComplexity >From a relatively shallow analysis, primes(n) appears to be O(n ** (3/2)), but it might be possible to tighten that up a bit with an analysis of the distribution of primes and their smallest divisors. > Do lists in Python 3 behave like ArrayList in Java (if the capacity > is full, then the array grows by more than 1 element) ? I believe the behavior in CPython is that if the array is full, the capacity is doubled, but I'm not certain, and that would be an implementation detail in any case. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
