Suppose we have an array A of n distinct integers, and we want to find both the minimal

and the maximal number. In Lecture $7$ we saw how to do this using $3$n

$2+$ O$(1)$ comparisons,

as opposed to the na$$ve algorithm that uses $2($n $1)$ comparisons by making two separate

passes to find the minimum and the maximum separately. Here, we will show that this

is actually optimal in the comparison model by proving a lower bound of $3$n

$2$ O$(1)($and

therefore the complexity of this problem is $3$n

$2+\backslash$Theta $(1)).$

For the lower bound, suppose there is an arbitrary comparison$-$based algorithm that finds

the minimum and maximum of A$.$ Suppose we run this algorithm on some input and consider

the situation after some step of the algorithm. Let us say that the element of the array has

lost comparison if it was compared with some other element and turned out to be smaller.

Let us say that the element has won comparison if it was compared to another element and

it turned out to be larger.