On Wed, Feb 15, 2012 at 10: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. > Do lists in Python 3 behave like ArrayList in Java (if the capacity > is full, then the array grows by more than 1 element) ?
Yes. Python lists aren't linked lists. list.append() resizes the underlying array intelligently to give O(1) performance, although I can't find any guarantee of this in the docs, but it is true in practice for all major Python implementations. Cheers, Chris -- http://mail.python.org/mailman/listinfo/python-list
