Finding the Min for positive and negative in python 3.3 list
Peter Otten
__peter__ at web.de
Wed Mar 13 08:00:26 EDT 2013
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.
More information about the Python-list
mailing list