On Wed, Mar 13, 2013 at 10:34 PM, Wolfgang Maier <wolfgang.ma...@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 -- http://mail.python.org/mailman/listinfo/python-list