How efficient is Python's max function

Question

The function max() which returns the maximum element from a list . . . what is its running time (in Python 3) in terms of Big O notation?

Solution 1

It's O(n), since it must check every element. If you want better performance for max, you can use the heapq module. However, you have to negate each value, since heapq provides a min heap. Inserting an element into a heap is O(log n).

Solution 2

Of course it is O(n) unless you are using a different datastructure supporting the max of a value collection due to some implementation invariant.

Solution 3

It depends on how you are using it. If you want to maximize based on a function "someFunc", it'll take O(len(l)*k) where k is the time function "someFunc" takes to run.

maxVal = max(l, key=somefunc)

But yes for normal case it should just iterate over the list and find the max using normal compare function.

Comments

[Greg Hewgill]

Inserting n elements into a heap is O(n log n).

[Matthew Flaschen]

@Greg, yes, I meant inserting a single element.

[phimuemue]

@Greg Hewgill: It is (at least if you implement it by yourself) possible to add n elements into a heap in O(n) (simply call siftdown for all elements in reverse order).

[pepr]

maximum element from a list... If the list is general (not sorted or otherwise organized, there is no way to get better than O(n) -- unless you have multiprocesor, parallel system.

[cessor]

I believe @pepr is right. Wouldn't I have to look at every item in the list anyway to add it to the heapq / priority queue, thus O(n)?