Question

Let \(P\) be an array containing \(n\) integers. Let \(t\) be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of \(n\) elements. Which one of the following choices is correct?

• A. \(t > 2n - 2\)
• B. \(t > 3\left\lceil \frac{n}{2} \right\rceil \text{ and } t \leq 2n - 2\)
• C. \(t > n \text{ and } t \leq 3\left\lceil \frac{n}{2} \right\rceil\)
• D. \(t > \lceil \log_2 n \rceil \text{ and } t \leq n\)

Hint:

The tournament method minimizes comparisons by pairing elements and tracking potential candidates for minimum and maximum.

Answer 1

The Correct Option is C

Step 1: Naive approach.
Finding minimum and maximum separately requires \(2n - 2\) comparisons, which is not optimal.

Step 2: Optimal comparison strategy.
Using the tournament method, elements are compared in pairs. Each comparison reduces the problem size efficiently.

Step 3: Counting comparisons.
The optimal number of comparisons required is at most \(3\left\lceil \frac{n}{2} \right\rceil - 2\), which is greater than \(n\) and less than or equal to \(3\left\lceil \frac{n}{2} \right\rceil\).

Step 4: Conclusion.
Thus, the correct bound on \(t\) is \(t > n\) and \(t \leq 3\left\lceil \frac{n}{2} \right\rceil\).

Final Answer: (C)