Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #41174

Re: Finding the Min for positive and negative in python 3.3 list

Show all headers | View raw

On Wed, Mar 13, 2013 at 10:34 PM, Wolfgang Maier
<wolfgang.maier@biologie.uni-freiburg.de> wrote:
> 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

Your sort is usually going to be O(n log n), not O(log n).

ChrisA

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Finding the Min for positive and negative in python 3.3 list Norah Jones <nh.jones01@gmail.com> - 2013-03-12 17:03 +0000
  Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 01:57 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 10:43 +0000
      Re: Finding the Min for positive and negative in python 3.3 list 88888 Dihedral <dihedral88888@googlemail.com> - 2013-03-14 04:45 -0700
      Re: Finding the Min for positive and negative in python 3.3 list 88888 Dihedral <dihedral88888@googlemail.com> - 2013-03-14 04:45 -0700
    Re: Finding the Min for positive and negative in python 3.3 list Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-03-13 11:23 +0000
      Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 14:12 +0000
        Re: Finding the Min for positive and negative in python 3.3 list Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-03-13 14:37 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 11:34 +0000
      Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 14:43 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Chris Angelico <rosuav@gmail.com> - 2013-03-13 22:36 +1100
    Re: Finding the Min for positive and negative in python 3.3 list Chris Angelico <rosuav@gmail.com> - 2013-03-13 22:38 +1100
    Re: Finding the Min for positive and negative in python 3.3 list Peter Otten <__peter__@web.de> - 2013-03-13 13:00 +0100
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 14:17 +0000

csiph-web