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?

To find both the minimum and maximum elements in an arbitrary array of $n$ elements simultaneously, the optimal algorithm pairs up elements and compares them:

1. Compare elements in pairs: $\lfloor n/2 \rfloor$ comparisons.

2. Compare the larger elements with the current maximum: $\lceil n/2 \rceil - 1$ comparisons.

3. Compare the smaller elements with the current minimum: $\lceil n/2 \rceil - 1$ comparisons.

The optimal number of comparisons (the lowest upper bound $t$) is:

• For even $n$: $1 + \frac{3(n-2)}{2} = \frac{3n}{2} - 2 = 3\lceil n/2 \rceil - 2$

• For odd $n$: $\frac{3(n-1)}{2} = 3\lfloor n/2 \rfloor$

In all cases, for $n \ge 2$:

Also, since finding just the minimum requires $n - 1$ comparisons and finding the maximum requires additional comparisons, we have $t > n$ for $n > 2$.

Thus, the correct inequality range is $t > n$ and $t \le 3\left\lceil \frac{n}{2} \right\rceil$.

Hence, the correct option is (C).