Finding the Min for positive and negative in python 3.3 list

[Mark Lawrence]

On 13/03/2013 14:12, Steven D'Aprano wrote:
> 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.
>

For the newbies hanging around there's Python's own Timsort which 
apparantly has worst case performance O(n log n), best case O(n) and 
average case O(n log n).  Please don't shoot the messenger :)



-- 
Cheers.

Mark Lawrence