12

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
  • 17,261
  • 40
  • 105
  • 135
ᴀʀᴍᴀɴ
  • 4,231
  • 7
  • 33
  • 53
  • Does this answer your question? [How efficient is Python's max function](https://stackoverflow.com/questions/5454030/how-efficient-is-pythons-max-function) – Spcogg the second May 15 '22 at 07:57

5 Answers5

28

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
  • 124,179
  • 11
  • 158
  • 228
  • 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
  • 73,231
  • 20
  • 109
  • 138
2

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
  • 21
  • 4
  • 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
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
  • 199,541
  • 138
  • 677
  • 738
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,581
  • 2
  • 33
  • 61