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?

Answer 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).

Answer 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.