29

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?

0

3 Answers 3

41

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

5
  • 9
    Inserting n elements into a heap is O(n log n). Mar 28, 2011 at 3:19
  • @Greg, yes, I meant inserting a single element. Mar 28, 2011 at 14:17
  • @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).
    – phimuemue
    Jul 21, 2011 at 21:37
  • 1
    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.
    – pepr
    May 6, 2012 at 21:54
  • 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)?
    – cessor
    Jan 9, 2017 at 1:46
3

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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.