Finding the Min for positive and negative in python 3.3 list

Wolfgang Maier wolfgang.maier at biologie.uni-freiburg.de
Wed Mar 13 12:34:08 CET 2013


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






More information about the Python-list mailing list