Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <oscar.j.benjamin@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.045
X-Spam-Evidence: '*H*': 0.91; '*S*': 0.00; 'algorithm': 0.04; 'elements.': 0.07; 'linear': 0.09; 'slices': 0.09; 'cc:addr :python-list': 0.11; "wouldn't": 0.14; 'cc:name:python list': 0.16; 'deletes': 0.16; 'elements': 0.16; 'wrote:': 0.18; 'seems': 0.21; '>>>': 0.22; 'cc:addr:python.org': 0.22; 'cc:2**0': 0.24; 'header:In-Reply-To:1': 0.27; 'message-id:@mail.gmail.com': 0.30; "d'aprano": 0.31; 'steven': 0.31; 'probably': 0.32; 'beginning': 0.33; 'subject:time': 0.33; 'could': 0.34; 'case,': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'list': 0.37; 'list.': 0.37; 'e.g.': 0.38; 'rather': 0.38; 'deleting': 0.60; 'gone': 0.61; 'length': 0.61; 'entire': 0.61; 'to:addr:gmail.com': 0.65; '2015': 0.84; 'complexity': 0.84; 'difference.': 0.84; 'oscar': 0.84; 'whereas': 0.91
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=DHIKhmmn3zbpSshew0BWr2hsz3nmFqU78TUkX84+RvU=; b=itMbFvLV9vfN/pkLjrwU28V1AnD2ZBn10V4jcPQzwYtcU4joI6vBCuBPCqkEtNWoed zKj8Iw8ZticqqPFO67udqgUUitCCwjjF9xLXefN95Fu1YxAdZda3ISX8QFxKFDi8tkV1 cpsPmqeiOh8WhxCTROjx3wExA/q1E1NbrfK2VWjEdWrYwjYHKS3sd7Z0kgqe/qk2c51l dTxXaj/47I6KpFjGGqPDLU80YTG/coq5RCx0Ke3OcT7UpGfK8dUJ7/DM4t8Y2TmuKkvP q5XdGCx+tRGq5XanB5FxynQfVdSrdmfH+kEbvPQ0eWKsZgTHtJmuiNW7LgPz281IVIfC L1Ag==
X-Received: by 10.180.218.108 with SMTP id pf12mr31324117wic.13.1432033809005; Tue, 19 May 2015 04:10:09 -0700 (PDT)
MIME-Version: 1.0
In-Reply-To: <mjf2fc$r4o$1@ger.gmane.org>
References: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com> <555b0621$0$2753$c3e8da3$76491128@news.astraweb.com> <mjf2fc$r4o$1@ger.gmane.org>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Tue, 19 May 2015 12:09:48 +0100
Subject: Re: Slices time complexity
To: Serhiy Storchaka <storchaka@gmail.com>
Cc: Python List <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.20+
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://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: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.128.1432033816.17265.python-list@python.org>
Lines: 22
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1432033816 news.xs4all.nl 2893 [2001:888:2000:d::a6]:49592
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:90840

On 19 May 2015 at 11:15, Serhiy Storchaka <storchaka@gmail.com> wrote:
> On 19.05.15 12:45, Steven D'Aprano wrote:
>>
>> On Tuesday 19 May 2015 05:23, Mario Figueiredo wrote:
>>>
>>>  From the above link it seems slices work in linear time on all cases.
>>
>>
>> I wouldn't trust that is always the case, e.g. deleting a contiguous slice
>> from the end of a list could be O(1).
>
> It always has linear complexity. You need to decref removed elements.

It has linear complexity in the length of the removed slice but not in
the length of the list. So deleting k elements from the end of a list
of length N is O(k) rather than O(N) which could be a big difference.
An algorithm that repeatedly deletes slices from the end until the
entire list was gone would still be O(N) whereas one that deletes from
the beginning would probably be O(N**2).

--
Oscar