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?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
kamikaze_pilot
  • 14,304
  • 35
  • 111
  • 171

3 Answers3

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

Community
  • 1
  • 1
Matthew Flaschen
  • 278,309
  • 50
  • 514
  • 539
  • 9
    Inserting n elements into a heap is O(n log n). – Greg Hewgill Mar 28 '11 at 03:19
  • @Greg, yes, I meant inserting a single element. – Matthew Flaschen Mar 28 '11 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 '11 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 06 '12 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 09 '17 at 01:46
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.

Taryn
  • 242,637
  • 56
  • 362
  • 405
pgrocks
  • 81
  • 1
  • 3
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.