17
votes

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?

3

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.

2
votes

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.