Finding the Min for positive and negative in python 3.3 list

[Chris Angelico]

On Wed, Mar 13, 2013 at 10:23 PM, Oscar Benjamin
<oscar.j.benjamin at gmail.com> 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.

Or looking at it another way: Sorting a list will require, at a bare
minimum, comparing every element against at least one other element -
if you could reduce it below that, there would be some element whose
position you cannot know. Finding the minimum requires precisely that
number of comparisons: each item against the one current minimum. :)

ChrisA