Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #20460

Re: Complexity question on Python 3 lists

References <franck-B0D585.19202115022012@news.free.fr>
From Ian Kelly <ian.g.kelly@gmail.com>
Date 2012-02-15 11:43 -0700
Subject Re: Complexity question on Python 3 lists
Newsgroups comp.lang.python
Message-ID <mailman.5843.1329331420.27778.python-list@python.org> (permalink)

Show all headers | View raw

On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter <franck@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Complexity question on Python 3 lists Franck Ditter <franck@ditter.org> - 2012-02-15 19:20 +0100
  Re: Complexity question on Python 3 lists Chris Rebert <clp2@rebertia.com> - 2012-02-15 10:35 -0800
  Re: Complexity question on Python 3 lists Ian Kelly <ian.g.kelly@gmail.com> - 2012-02-15 11:43 -0700
  Re: Complexity question on Python 3 lists Dave Angel <d@davea.name> - 2012-02-15 13:45 -0500
  Re: Complexity question on Python 3 lists Stefan Behnel <stefan_ml@behnel.de> - 2012-02-15 20:01 +0100
  Re: Complexity question on Python 3 lists Chris Rebert <clp2@rebertia.com> - 2012-02-15 11:11 -0800
  Re: Complexity question on Python 3 lists Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-02-15 15:28 -0500
  Re: Complexity question on Python 3 lists Terry Reedy <tjreedy@udel.edu> - 2012-02-15 16:41 -0500
  Re: Complexity question on Python 3 lists Ian Kelly <ian.g.kelly@gmail.com> - 2012-02-15 15:54 -0700
  Re: Complexity question on Python 3 lists Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-02-16 00:41 +0000

csiph-web