I've found that max
is slower than the sort
function in Python 2 and 3.
Python 2
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 239 usec per loop
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)'
1000 loops, best of 3: 342 usec per loop
Python 3
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 252 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)'
1000 loops, best of 3: 371 usec per loop
Why is max
(O(n)
) slower than the sort
function (O(nlogn)
)?
a.sort()
works inplace. Trysorted(a)
O(n)
memory and max(a) needs only onesort
sorts, and thena
is sorted forevern-1
comparisons on an already sorted list, which is the same number asmax
has to do. In fact Timsort will do O(n) comparisons even when the input is "partially sorted". Other algorithms may require O(nlogn) time even in the sorted case.