Wolfgang Maier 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),
O(n*log(n)) according to <http://wiki.python.org/moin/TimeComplexity> > 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. That's not how big-O math works. 2*O(n) is still O(n). 2*O(n) == O(n) As n grows an O(log(n)) approach will eventually be faster than O(n), but that's asymptotical behaviour and allows for an arbitrary constant factor. For a given n you cannot decide if the O(n) or the O(log(n)) algorithm is faster unless you know these constant factors. Put another way: Iterating twice over the list doubles an unknown constant factor. -- http://mail.python.org/mailman/listinfo/python-list