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 method analysis.
If we find the minimum and maximum separately in an array of n elements, it requires:

(n − 1) comparisons to find the minimum and
(n − 1) comparisons to find the maximum

Total comparisons = 2n − 2, which is not optimal.

---

Step 2: Optimal comparison strategy.
Using the tournament method, elements are compared in pairs.

Each comparison simultaneously helps determine candidates for minimum and maximum, reducing redundant comparisons.

---

Step 3: Count the number of comparisons.
With the optimal strategy, the number of comparisons required is:

3⌈n / 2⌉ − 2

This value is:

• Strictly greater than n
• Less than or equal to 3⌈n / 2⌉

---

Step 4: Final conclusion.
Therefore, the correct bound on the number of comparisons t is:

t > n and t ≤ 3⌈n / 2⌉

Final Answer: (C)