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:2**0': 0.21; 'header:In-Reply-To:1': 0.22; 'feb': 0.22; 'knowing': 0.23; 'sfxlen:0': 0.23; 'smallest': 0.23; 'cc:2**0': 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>
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

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