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?
17
votes
3 Answers
28
votes
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).
3
votes
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.