Finding the Min for positive and negative in python 3.3 list

[Steven D'Aprano]

On Wed, 13 Mar 2013 11:34:08 +0000, 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), 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.

Not quite. In general, Big Oh values add by taking the *largest* term.

Calling min() twice is O(n) + O(n) or 2*O(n), which is just O(n) since 
Big Oh analysis ignores any multiplicative constant.

Sorting in general is O(n*log n), not O(n). If you have arbitrary, 
unsorted data, then sorting it first and then bisecting is O(n*log n) + 
O(log n), which is just O(n*log n), which is slower than O(n).

Since Big Oh doesn't tell you the actual physical cost of operations, or 
how long they take, beware of relying too much on Big Oh analysis without 
doing actual physical timings.

And in practice, min() is such a straight-forward, simple operation that 
it is hard to imagine anything beating it under normal circumstances. 
Unless you have truly vast amounts of data, the simplest solution is 
usually the best.


-- 
Steven