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 minimun 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[\frac{n}{2}\right]$ and t $\le$ 2n - 2
• C. t > n and t$\le 3\left[\frac{n}{2}\right]$
• D. t > $\lceil lo{g}_2\left(n\right)\rceil$ and t $\le n$

Answer 1

The correct option is C t > n and t$\le 3\left[\frac{n}{2}\right]$

Using divide and conquer min-max algo , w number of comparisons =$\frac{3n}{2}-2$.

Hence $\frac{3n}{2}-2$ will lie in the range of n to 3[$\frac{n}{2}]$.
Hence option (a) is the correct answer.