GATE CS 2007 Q50 — Asymptotic Worst Case Time and Space Complexity

To find both the maximum and minimum elements in an array of $n$ numbers (where $n$ is even), we can use an optimal pairwise comparison algorithm to minimize the number of comparisons:

1. Initialize: Compare the first two elements of the array. Assign the larger element to max and the smaller element to min.
   This requires $1$ comparison.
2. Process Remaining Elements: Group the remaining $n - 2$ elements into pairs. There will be $\frac{n - 2}{2}$ pairs. For each pair:
   • Compare the two elements of the pair with each other to find the local maximum and local minimum ($1$ comparison).
   • Compare the local maximum with the global max ($1$ comparison).
   • Compare the local minimum with the global min ($1$ comparison).
   Thus, each of the $\frac{n - 2}{2}$ pairs requires exactly $3$ comparisons.

Summing these up, the total number of comparisons is:

Since we can achieve this with exactly $1.5n - 2$ comparisons, it is true that at most $1.5n - 2$ comparisons are needed.