Groups > comp.lang.python > #20460

Re: Complexity question on Python 3 lists

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<ian.g.kelly@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.001
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'cpython': 0.05; 'subject:Python': 0.05; 'behave': 0.07; 'see:': 0.07; 'python': 0.08; 'append': 0.09; 'am,': 0.12; 'url:moin': 0.12; 'case.': 0.15; 'amortized': 0.16; 'shallow': 0.16; 'cc:addr:python-list': 0.16; 'subject:question': 0.16; 'wed,': 0.17; 'wrote:': 0.18; 'appears': 0.19; 'cheers,': 0.20; 'java': 0.21; 'cc:no real name:20': 0.21; 'header:In-Reply-To:1': 0.22; 'feb': 0.22; 'knowing': 0.23; 'sfxlen:0': 0.23; 'smallest': 0.23; 'cc:20': 0.26; 'mainly': 0.28; 'lists': 0.28; 'bit': 0.28; "i'm": 0.28; 'message-id:@mail.gmail.com': 0.29; 'cc:addr:python.org': 0.29; 'url:wiki': 0.29; 'array': 0.30; 'calling': 0.34; 'url:python': 0.35; 'received:209.85.214': 0.36; 'subject:lists': 0.36; 'but': 0.37; 'received:google.com': 0.37; 'received:209.85': 0.38; 'relatively': 0.39; 'url:org': 0.39; 'received:209': 0.39; 'might': 0.40; 'more': 0.61; 'below': 0.62; 'believe': 0.65; 'analysis': 0.77; 'certain,': 0.84
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=tEq3r7lE0cJ5g+koPczi89CcaKuNtHM6uUErCjUbTeQ=; b=aE3kCgN3MX5+5a2uahBuC6O7UZ1DHH9o8noukpjiAoj5WrOzef7XiFWBRwAUTuhPq4 FgYtH+ESXJ5jzXJIhlIVU0esAqq0AVMzbq33nHB0yOhuQgedw+Edz5rwTV0K7xm5h1dP JTzJsl0Ym9HrmQdJgAVl/n3IWw69uBh7qgYQw=
MIME-Version	1.0
In-Reply-To	<franck-B0D585.19202115022012@news.free.fr>
References	<franck-B0D585.19202115022012@news.free.fr>
From	Ian Kelly <ian.g.kelly@gmail.com>
Date	Wed, 15 Feb 2012 11:43:09 -0700
Subject	Re: Complexity question on Python 3 lists
To	Franck Ditter <franck@ditter.org>
Content-Type	text/plain; charset=ISO-8859-1
Cc	python-list@python.org
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.12
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.5843.1329331420.27778.python-list@python.org> (permalink)
Lines	21
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1329331420 news.xs4all.nl 6946 [2001:888:2000:d::a6]:55891
X-Complaints-To	abuse@xs4all.nl
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:20460

Show key headers only | 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

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