Proof for the minimum number of comparisons required to get the maximum AND minimum element of an array. For any $N$-sized array, I would like to prove that the minimum number of comparisons to find both the max and min element simultaneously is
\begin{align}
\frac{3N}{2} - 2 && \text{N: even} \\
\frac{3(N-1)}{2} && \text{N: odd}
\end{align}
It's clear to me that the above number of comparisons can guarantee that the minimum and maximum can be found. For the even case, all you need to do is consider $N/2$ distinct pairs (by distinct pairs, I just mean that no 2 pairs have any of the same elements). For each pair $(a,b)$, you find $x = \max(a,b)$ and $y = \min(a,b)$. Then you compare $x$ with the running max and y with the running y. So for each pair, excluding the first pair, we require 3 comparisons. For the first pair, we don't need to compare $x$ with the running max and y with the running y because the running max and min can be set to $x$ and $y$, respectively, since it wasn't initialized already. Hence why we have $-2$ in the answer.
For an odd $N$, the idea is the same, except the last element cannot be paired. So we have $(N-1)/2$ pairs, giving us $\frac{3(N-1)}{2} - 2$ comparisons, and the last element adds 2 comparisons, giving us $\frac{3(N-1)}{2}$.
Okay, but I don't know how to show that you cannot do any better than the above. How can I prove that the above bounds are lower bounds?
 A: The following diagram illustrates the $3$ steps involved in finding the minimum and maximum of array using comparisons.

There are two observations to be made:

*

*Any comparison between two elements of the array will result in either a winner(larger) and a loser(smaller). It is indicated by the yellow step.

*There is no direct way to make one comparison(between two elements) and conclude some element is the maximum or the minimum in the yellow step.

*Now, this results into two subsets: one of local maximas(sort of) elements and another of local minimas(sort of) elements.

*Then in the red step, we find the global minima and global maxima elements.

If looked carefully, any comparison-based finding of maximum and minimum element from an unsorted array, has these three steps(sometimes implicitly).
Let's bound, for the even $n$ case(odd $n$ can be done similarly):

*

*The yellow step can be done in $\geq \frac{n}{2}$ number of steps. Since, $\frac{n}{2}$ is the minimum number of comparisons one can do out of $n$ elements(Why? Compare any two elements and remove both these elements from the array, then compare next two and remove, so on..).

*The blue and red step of finding the maximum and the minimum, as already pointed out by O.P. can be done on these arrays of size $\frac{n}{2}$ resulting from the yellow step in $\geq\frac{n}{2}-1$ many comparisons each.

This results in the lower bound of $\frac{3n}{2}-2$, which we show in an python implementation below that it can be attained.
def max_min(arr):
    
    n = len(arr)
    max_element = min_element = arr[0]
    
    for i in range(n//2):
        if arr[i] > arr[n-i-1]:
            arr[i], arr[n-i-1] = arr[n-i-1], arr[i]
    
    for i in range(n//2):
        if min_element > arr[i]:
            min_element = arr[i]
        if max_element < arr[(n//2)+i+(n%2 == 1)]:
            max_element = arr[(n//2)+i+(n%2 == 1)]
            
    return max_element, min_element
```

