Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <python-python-list@m.gmane.org>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.004
X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'algorithm': 0.03; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'subject:python': 0.11; 'algorithm.': 0.16; 'benjamin': 0.16; 'bisect': 0.16; 'bit.': 0.16; 'message-id:@post.gmane.org': 0.16; 'n),': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'sorting': 0.16; 'subject:3.3': 0.16; 'sort': 0.21; 'bit': 0.21; 'header:User-Agent:1': 0.26; 'wrote': 0.26; 'first.': 0.27; 'header:X-Complaints-To:1': 0.28; 'subject:list': 0.28; 'received:132': 0.29; 'writes:': 0.29; 'to:addr:python-list': 0.33; 'minimum': 0.34; 'thanks': 0.34; 'list': 0.35; 'faster': 0.35; 'so,': 0.35; 'received:org': 0.36; 'but': 0.36; 'should': 0.36; 'charset:us-ascii': 0.36; 'two': 0.37; 'subject:: ': 0.38; 'performance': 0.39; 'to:addr:python.org': 0.39; 'takes': 0.39; 'header:Received:5': 0.40; 'course.': 0.62; 'each,': 0.84; 'oscar': 0.84; 'subject:Min': 0.84
X-Injected-Via-Gmane: http://gmane.org/
To: python-list@python.org
From: Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de>
Subject: Re: Finding the Min for positive and negative in python 3.3 list
Date: Wed, 13 Mar 2013 11:34:08 +0000 (UTC)
References: <mailman.3239.1363109618.2939.python-list@python.org> <513fdcfc$0$29965$c3e8da3$5496439d@news.astraweb.com> <loom.20130313T111109-885@post.gmane.org> <CAHVvXxSLADKHqDZYpjL0o17QJ+XMjD+_0Qeg26439PSWBKamgw@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Gmane-NNTP-Posting-Host: sea.gmane.org
User-Agent: Loom/3.14 (http://gmane.org/)
X-Loom-IP: 132.230.1.31 (Mozilla/5.0 (Windows NT 6.1; rv:19.0) Gecko/20100101 Firefox/19.0)
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.3261.1363174467.2939.python-list@python.org>
Lines: 22
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1363174467 news.xs4all.nl 6914 [2001:888:2000:d::a6]:52025
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:41172

Oscar Benjamin <oscar.j.benjamin <at> gmail.com> writes:

> 
> 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
> 

Oops, you're right of course.
Wrote this in a hurry before and got confused a bit.
So, the two min()s take O(n) each, the sort takes O(n),
but the bisect takes O(log n),
which means that sorting and bisecting together should still be faster
than 2xmin(), although it's a bit less striking than what I wrote first.
Thanks for the correction,
Wolfgang