15

What is the big O of the min and max functions in Python? Are they O(n) or does Python have a better way to find the minimum and maximum of an array? If they are O(n), isn't it better to use a for-loop to find the desired values or do they work the same as a for-loop?

Uyghur Lives Matter
  • 18,820
  • 42
  • 108
  • 144
ᴀʀᴍᴀɴ
  • 4,443
  • 8
  • 37
  • 57
  • Does this answer your question? [How efficient is Python's max function](https://stackoverflow.com/questions/5454030/how-efficient-is-pythons-max-function) – Hansang May 15 '22 at 07:57

5 Answers5

35

It's O(n). It's a general algorithm, you can't find the max/min in the general case without checking all of them. Python doesn't even have a built-in sorted collection type that would make the check easy to specialize.

A for loop would have the same algorithmic complexity, but would run slower in the typical case, since min/max (on CPython anyway) are running an equivalent loop at the C layer, avoiding bytecode interpreter overhead, which the for loop would incur.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • 1
    I heard some of algorithm dosen't need to compare all values of an array to sort it , they use satistical information , for example range of numbers in array like Counting sort and bucket sort – ᴀʀᴍᴀɴ Feb 13 '16 at 23:30
  • @Arman_Immortal The lower bound for sorting is O(n log n) if you cannot assume anything about your data. Why are we talking about sorting now? – timgeb Feb 13 '16 at 23:32
  • 6
    @Arman_Immortal: Those are sorting algorithms, not for finding a single minimum or maximum, and even count sort with restricted input ranges is `O(n)`; it still has to work with every element in the input, even if it doesn't have to compare them to each other. If the input doesn't have known pre-existing order or structure of some kind, you can't improve on `O(n)` for finding the `min` or `max`. – ShadowRanger Feb 13 '16 at 23:34
  • @timgeb I mean maybe Python store some information about an array then find min and max using them and dont find it with compare all vales – ᴀʀᴍᴀɴ Feb 13 '16 at 23:34
  • 1
    @Arman_Immortal: It does not. That would slow all other use cases for a very limited benefit. Python `list` and `tuple` are flat storage with no special features, and `max`/`min` don't even specialize to those types; they handle general iterable inputs, which might not even have a pre-existing known length. – ShadowRanger Feb 13 '16 at 23:35
  • @ShadowRanger Yeah you right , Thanks for your answer! it would be accepted – ᴀʀᴍᴀɴ Feb 13 '16 at 23:36
9

To find the maximum or minimum of a sequence, you must look at each element once, thus you can't get better than O(n).

Of course, Python min and max have O(n) too: docs.

You can write your own min/max function with a for loop and it will have the same complexity, but will be slower because it is not optimized in C.

timgeb
  • 76,762
  • 20
  • 123
  • 145
  • Link to the actual documentation should be the correct answer, everyone else's is just speculative. – Hansang May 15 '22 at 07:57
  • *Technically*, negative infinity is the smallest possible float, 0 is the smallest possible unsigned int, and there are a range of smallest signed ints based on the size. So if you saw one of those you could break early and not look at every element once. That would still be an O(n) operation however, and doing those checks would add cycles so I don't believe most fast implementations do that. – Scott Sep 28 '22 at 23:26
0

They are both O(n) and there is no way to find min max in an array. Actually the underlying implementation of min/max is a for loop.

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
0

As already stated in the (theoretically) general case finding the minimum or maximum of a unsorted collection of values requires you to look at each value (thus O(N)), because if you wouldn't look at a value, that value could be greater than all other values of your collection.

[..] isn't it better to use a for-loop to find the desired values or do they work the same as a for-loop?

No. Programming is about abstraction: Hiding details of implementation (that loop) behind a fancy name. Otherwise you could write that loop in assembly, couldn't you?

Now for the "special" case: We normally don't work with arbitrary large numbers. Assume a 2 bit unsigned integer: The only possible values are 0, 1, 2 and 3. As soon as you find a 3 in some (arbitrary large) collection you can be certain that there will be no larger value. In a case like that it can make sense to have a special check to know whether one already found the maximum (minimum) possible value.

Daniel Jour
  • 15,896
  • 2
  • 36
  • 63
0

For time complexity O(1) You can use this:

minimum = y ^ ((x ^ y) & -(x < y)); // min(x, y)

maximum = x ^ ((x ^ y) & -(x < y)); // max(x, y)

Ayush Rawat
  • 17
  • 5
  • 1
    This does not provide an answer to the question. Once you have sufficient [reputation](https://stackoverflow.com/help/whats-reputation) you will be able to [comment on any post](https://stackoverflow.com/help/privileges/comment); instead, [provide answers that don't require clarification from the asker](https://meta.stackexchange.com/questions/214173/why-do-i-need-50-reputation-to-comment-what-can-i-do-instead). - [From Review](/review/late-answers/30845946) – Register Sole Jan 21 '22 at 03:30