Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!ecngs!feeder2.ecngs.de!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!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.020
X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'algorithm': 0.03; 'cc:addr :python-list': 0.10; 'subject:python': 0.11; 'algorithm.': 0.16; 'bisect': 0.16; 'cc:name:python list': 0.16; 'sorting': 0.16; 'subject:3.3': 0.16; 'wrote:': 0.17; 'certainly': 0.17; 'suggested': 0.20; 'sort': 0.21; 'cc:2**0': 0.23; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'first,': 0.27; 'message-id:@mail.gmail.com': 0.27; 'subject:list': 0.28; 'run': 0.28; 'faster,': 0.29; 'function': 0.30; 'running': 0.32; 'zero': 0.33; 'received:google.com': 0.34; 'minimum': 0.34; 'list': 0.35; 'faster': 0.35; 'received:209.85.220': 0.35; 'received:209.85': 0.35; 'two': 0.37; 'received:209': 0.37; 'far': 0.37; 'subject:: ': 0.38; 'performance': 0.39; 'takes': 0.39; 'your': 0.60; 'easy': 0.60; '2013': 0.84; 'oscar': 0.84; 'subject:Min': 0.84
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=yC2jbFW65gF8N/ytL740ECdvp4EiX+ci4Y98OFkPyDk=; b=ihAVIiVXqv7vlqL5RIZ1p7SmLLb9OiaBZgfjpBOCt9vcTAh8ZC7tCNTzzeS1FFIB+u yRNzhRb84Wo+1BlFVXuUGv8a/UiRf7m0fWigBI12H5b0FMIbB4kgDayMXyh9wU/mcs4f wX3adR3Su8Zn1NrQSuXLyYrK62FBtz1uzTbuq6NDVaCWtF+Q63CY/bHkTINF0hzoAQZR ewyMn8CulVVPxBNdjxryr1uVmiT73FkZAAFzC3BzMAnwBwVemnjJ8LQdKEfYZ20T2ieZ XVbDpdTgkU12kul/GMLxTkPEwXF8FsPsVPAw0nEZeJHOZaT6Qcimur7SheMKu1Esa30b djrg==
X-Received: by 10.220.248.134 with SMTP id mg6mr3833862vcb.2.1363173822804; Wed, 13 Mar 2013 04:23:42 -0700 (PDT)
MIME-Version: 1.0
In-Reply-To: <loom.20130313T111109-885@post.gmane.org>
References: <mailman.3239.1363109618.2939.python-list@python.org> <513fdcfc$0$29965$c3e8da3$5496439d@news.astraweb.com> <loom.20130313T111109-885@post.gmane.org>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Wed, 13 Mar 2013 11:23:22 +0000
Subject: Re: Finding the Min for positive and negative in python 3.3 list
To: Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de>
Content-Type: text/plain; charset=ISO-8859-1
Cc: Python List <python-list@python.org>
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
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.3260.1363173832.2939.python-list@python.org>
Lines: 17
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1363173832 news.xs4all.nl 6961 [2001:888:2000:d::a6]:49166
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:41171

On 13 March 2013 10:43, Wolfgang Maier
<wolfgang.maier@biologie.uni-freiburg.de> wrote:
>
> thinking again about the question, then the min() solutions suggested so far
> certainly do the job and they are easy to understand.
> However, if you need to run the function repeatedly on larger lists, using min()
> is suboptimal because its performance is an O(n) one.
> It's faster, though less intuitive, to sort your list first, then use bisect on
> it to find the zero position in it. Two manipulations running at O(log(n)).

Sort cannot be O(log(n)) and it cannot be faster than a standard O(n)
minimum finding algorithm. No valid sorting algorithm can have even a
best case performance that is better than O(n). This is because it
takes O(n) just to verify that a list is sorted.


Oscar