In class we showed using an adversary argument that any algorithm

to compute the MAX and the MIN of a set of n distinct numbers

simultaneously using pairwise comparisons must, in the worst$-$case, use

at least $3$n$/22$ comparisons.

$($a$)$ Use the decision tree argument $($finding a lower bound on the num$-$

ber of possible responses, which is a lower bound on the number

of leaves, and using this as a bound on the height of the tree$)$

to develop a worst$-$case lower bound on the number of pairwise

comparisons.

$($b$)$ If this bound is different than $3$n$/22,$ explain how seemingly

contradictory bounds can both be correct.