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

Groups > comp.lang.python > #41172

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

Show all headers | View raw

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

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