Finding the Min for positive and negative in python 3.3 list

[Steven D'Aprano]

On Wed, 13 Mar 2013 11:23:22 +0000, Oscar Benjamin wrote:

> On 13 March 2013 10:43, Wolfgang Maier
> <wolfgang.maier at biologie.uni-freiburg.de> wrote:
>>
>> thinking again about the question, then the min() solutions suggested
>> so far certainly do the job and they are easy to understand. However,
>> if you need to run the function repeatedly on larger lists, using min()
>> is suboptimal because its performance is an O(n) one. It's faster,
>> though less intuitive, to sort your list first, then use bisect on it
>> to find the zero position in it. Two manipulations running at
>> O(log(n)).
> 
> 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.

That's almost true. It applies to comparison sorts, that is, the kind of 
sort algorithm where you have to compare the elements being sorted to 
know where they go. But it doesn't necessarily apply to non-comparison 
sorts. For example, Bead sort could in principle operate in O(sqrt(n)) 
time, or even O(1), although in practice it is O(n).

Another example is Bitonic sort, which is O(log(n)**2).

In practical terms though, you are right. There is no practical, general 
purpose sorting algorithm that can beat O(n) for arbitrary lists of data.



-- 
Steven