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 -- http://mail.python.org/mailman/listinfo/python-list
