It is not difficult to devise an algorithm that can find both the minimum and the maximum of n elements using Θ(n) comparisons. Simply find the minimum and maximum independently, using n – 1 comparisons for each, for a total of 2n – 2 comparisons.In fact, at most 3(n/2) comparisons are sufficient to find both the minimum and the maximum in the array of size n.We compare pairs of elements from the input first with each other, and then we compare the smaller to the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.
Continue reading “Select maximum and minimum using 3*(n/2) comparisons”