Finding the Min for positive and negative in python 3.3 list
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.
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,
More information about the Python-list