Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!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.011
X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'singh': 0.07; 'python': 0.08; 'pm,': 0.10; 'binary': 0.14; 'wrote:': 0.14; 'inserting': 0.16; 'n),': 0.16; 'somewhere': 0.17; 'subject:list': 0.19; 'insert': 0.19; 'header:In-Reply-To:1': 0.21; 'memory': 0.22; 'fri,': 0.23; 'received:209.85.161.46': 0.23; 'received:mail- fx0-f46.google.com': 0.23; 'received:209.85.161': 0.26; 'correct': 0.28; 'message-id:@mail.gmail.com': 0.28; 'lists': 0.29; 'second': 0.30; 'arrays': 0.30; 'value.': 0.32; 'to:addr:python-list': 0.33; 'list': 0.33; "isn't": 0.33; '17,': 0.35; 'actual': 0.36; 'received:google.com': 0.37; 'received:209.85': 0.37; 'but': 0.38; 'implemented': 0.38; 'subject:: ': 0.38; 'received:209': 0.39; 'finding': 0.39; 'to:addr:python.org': 0.39; 'here': 0.66; 'subject:Best': 0.91
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:from:date :message-id:subject:to:content-type; bh=gNnXa2CIN+ndZK9laXzNDikTMflUbzB3hgX2cCRVYOQ=; b=xmnRrbj2zIxdTFcQcv4Z4ZyIE6QIZDELB/0wTbFwJb8CvUxWSoKOhb/6rYaka5GVru IAFKpJZxmbVOZsZP/2KvspgDt+1CIimOvJHdReXPuncOW2Ixa43lqtnGP62x3MdUX6xN 6ymUpGI5nPZkkoBJUiNdIG+/Ot+rCYFWYvUuY=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; b=RLu4XDgR4/7/LlgtjeWFK44VGxorlGZwDqSoDjlCA2cBQjSDt+sIMLLGG1GtW9Md8I 5N66hjaflbBdLZ6Mo46KQmQ3q4fmK5FZ/Cjcmg4Y+YF+8eFYuwa3LhfbViBit7mHT7J5 /23PpydACTDlZTMTPCjiw51s61RHluM/xJh9E=
MIME-Version: 1.0
In-Reply-To: <BANLkTin-76BecXqwnHCaegYQyQ24gsp9BQ@mail.gmail.com>
References: <c63e771c-8968-4d7a-9c69-b7fa6ff34e09@35g2000prp.googlegroups.com> <BANLkTin-76BecXqwnHCaegYQyQ24gsp9BQ@mail.gmail.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Fri, 17 Jun 2011 15:23:54 -0600
Subject: Re: Best way to insert sorted in a list
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
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.93.1308345873.1164.python-list@python.org>
Lines: 11
NNTP-Posting-Host: 82.94.164.166
X-Trace: 1308345873 news.xs4all.nl 49044 [::ffff:82.94.164.166]:56340
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7860

On Fri, Jun 17, 2011 at 3:02 PM, Shashank Singh
<shashank.sunny.singh@gmail.com> wrote:
> Correct me if I am wrong here but isn't the second one is O(log N)?
> Binary search?
> That is when you have an already sorted list from somewhere and you
> are inserting just one new value.

Finding the position to insert is O(log n), but the actual insert is
O(n).  This is because Python lists are implemented with arrays and
everything after the inserted item has to be moved in memory to make
space for the insert.