Let P be an array containing \(n\) integers. Let \(t\) be the lowest upper…
2021
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 \lceil{\frac {n} {2} \rceil} and \ t \leq 2n - 2\) - C.
\(t > n \ \ and \ t \leq 3\lceil {\frac {n}{2}} \rceil\) - D.
\(t > \lceil {log_2 (n)} \rceil and \ t \leq n\)
Attempted by 85 students.
Show answer & explanation
Correct answer: C
Key idea: use pairwise comparisons to bound the worst-case number of comparisons and state the tight bound.
Pairwise algorithm: process the array in pairs. For each pair, first compare the two elements (1 comparison). Then compare the larger to the current maximum and the smaller to the current minimum (2 more comparisons).
Count of comparisons: if n is even (n = 2k), after an initial pair you do 1 + 3*(k-1) = 3n/2 - 2 comparisons. If n is odd (n = 2k + 1), you do 3k = 3(n - 1)/2 comparisons. Both cases equal the formula 3⌈n/2⌉ - 2 when n > 1.
Tightness (short justification): the pairwise method achieves 3⌈n/2⌉ - 2 comparisons in the worst case, and a standard adversary/counting argument shows no algorithm can always do fewer in the worst case. Thus the worst-case minimum number of comparisons needed to determine both minimum and maximum equals 3⌈n/2⌉ - 2.
Conclusion: the statement that t > n and t ≤ 3⌈n/2⌉ is correct among the provided choices, but it can be tightened to the exact worst-case value t = 3⌈n/2⌉ - 2. Therefore the choice asserting t > n and t ≤ 3⌈n/2⌉ is the best match from the given options, with the extra note that the sharp bound is 3⌈n/2⌉ - 2.