How many comparisons does a max() or a min() function do?

Question

Given a list of n numbers, what is the number of comparison that the min() or max() function in python does? If this is not optimal, how can I design a function that performs the least comparison?

Answer 1

The built-in min() and max() iterate over the list once, performing n-1 comparisons (the first element with the second, then the larger of the first two with the third and so on). This is O(n) in big-O notation.

Unless you know something about your list (such as that it's ordered in a certain way) you can't do better than O(n): any element can be the smallest or the largest and therefore needs to be looked at.

Here is a simplified and annotated version of the loop that's used by both min() and max():

it = PyObject_GetIter(v); /* v is the list */
maxitem = NULL; /* the result */
maxval = NULL;  /* the value associated with the result, always
                   the same as maxitem in this simplified version */
while (( item = PyIter_Next(it) )) {
    /* maximum value and item are unset; set them */
    if (maxval == NULL) {
        maxitem = item;
        maxval = item;
    }
    /* maximum value and item are set; update them as necessary */
    else {
        int cmp = PyObject_RichCompareBool(val, maxval, op); /* op is Py_LT or Py_GT */
        if (cmp > 0) {
            maxval = val;
            maxitem = item;
        }
    }
}

(source code.)

If you need to repeatedly find and remove the smallest, or the largest, element in a collection, and this dominates the runtime of your overall algorithm, it might be worth looking at data structures other than a list.

One data structure that immediately springs to mind is a binary heap. It offers O(n logn) insertion and O(n logn) removal of the smallest (largest) element. Python has an implementation in its heapq module.