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=|N|. After comparisons were done, let N' be the items not compared yet and let n'=|N'|. Let W be all numbers that always were larger when compared (alwayswon) 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 =|B'|. Note that for any algorithm at any time n=n+b+w+L since these sets are disjoint.

1.) Recall that n=|N|, w=|W|, l`=|L|, and consider 3n+ 2w+ 2l`. Show that this term before the algorithm starts is 3n and when the algorithm ends its 4.

2.) Show that the number of comparisons needed to find the maximum and the minimum in the worst case (only using comparisons) is at least [(3n4)/2].