Here's a tricky question:

When you compute the minimum of N things, whether you use the recursive version or the iterative version, you'll end up performing about N comparisons. How many comparisons are needed to compute both the minimum and the maximum?

If you were the original poster I would suspect homework, but since you're not...

How many are needed depends on what you already know.

If you know the collection is already sorted you can use the endpoints. No comparisons are needed.

If the collection is unsorted and you already know the value but are searching for them in a collection, the average number of comparisons is 1/2 of the collection size and the worst case of comparisons is the full container size. Since you must do this for both minimum and maximum, will be N on average and 2N worst case.

If the collection is unsorted and the maximum and minimum are unknown then it requires a comparison against every element. The number of comparisons is equal to the number of elements in the collection minus one (the first element starts as the initial best value). Since the problem's definition requires a test against every element, N-1 is the lowest bound on the number of comparisons for a single pass.

If you want both the minimum and maximum value it depends on if you are performing two operations or one. You will need two comparisons for each, one against the best known minimum and another against the best known maximum. A few microprocessors provide CPU instruction that performs both tests, and I'm not sure if you would count that as one comparison or two. Either way, for the situations game developers usually care about doing this on a single core and a flat array will be most efficient to simply walk the list; cache effects will come into play and a simple linear traversal will result in both the minimum number of comparisons and good clock time.

The minimum number of comparisons does not always equate to most efficient for a situation.

Most of us have multiple processors available. Large data sets that span multiple devices offer non-uniform memory speeds and parallel space options. You can exchange linear time and linear space for parallel time or parallel space for a small cost.

If multiple processors are available you can partition the work among the processors you might run a pass on each partition in parallel, gather the work together, and run a second pass against the results of each partition. Similarly there are SIMD instructions you could perform on a single processor. When access time is not constant, such as having terabytes of data spread across data tapes rather than disk drives, a similar partition may make sense. There are several algorithms such as QuickSelect that may make sense in those situations as you can exchange time and space in data processing.

You will perform more comparisons in these cases but likely complete the search in less clock time.

**Edited by frob, 30 January 2014 - 02:10 PM.**

Realized I needed a bit of clarification.