Question 1: Consider the problem of finding both the maximum and the minimum. We will show that you can not find them both in less than (about) 3n/2 comparisons. Consider the run of any algorithm and defined the following sets that depend on the comparison the algorithm chose. Let N be the collection of numbers. We denote n = INI. After comparisons were done, let N' be the items not compared yet and let n' = INI. Let W be all numbers that always were larger when compared (always "won") in all the comparisons, and let its size be w. Let L be the set of numbers who always "lost" (where always smaller) when compared and lets its size be l. Let B be the set of those who both lost least once and won at least once and let b IBI. Note that for any algorithm at any time n = n' + b+ w + 1 since these sets are disjoint 1. Show that there is always an input so that if a member u W is compared to a 2. Show that there is an input so that if a member uE L is compared to a number 3. Show that when the algorithm stops, there is exactly one element in W, exactly 4. Recall that n' = IN". w = IWI, 1 = IL. and consider 3n' + 2w + 21. Show that nparisons needed to find the maximum and the min- number not in W, u wins. not in L, u looses. one element in in L and the rest of the elements belong to B this term before the algorithm starts is 3n and when the algorithm ends its4 imum in the worst case (only using comparisons) is at least (3n - 4)/2