Question

Disclaimer: This is just One question with multiple parts. It is not multiple questions in one post.

Question:

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 W be all numbers that only ”won” (always were larger) in all the comparisons, and let its size be w. Let L be the set of numbers who always ”lost” and lets its size be `. Let B be the set of those who both lost least once and won at least once.

1. Show that there is always an input so that if a member u ∈ W is compared to a
number not in W , u wins.

2. Show that there is an input so that if a member u ∈ L is compared to a number
not in L, u looses.

3. Show that when the algorithm stops, there is exactly one element in W , exactly
one element in in L and the rest of the elements belong to B.

4. Recall that n = |N |, w = |W |, ` = |L|, and consider 3n + 2w + 2`. Show that at
start the value is 3n and at the end at the end its 4

5. Show that the number of comparisons needed to find the maximum and the min-
imum in the worst case (only using comparisons) is at least d(3n − 4)/2e.

Answer 1

1. Show that there is always an input so that if a member u ∈ W is compared to a number not in W , u wins.

Now if we consider that u loses to a number (say num) not in W then num can't be part of L as L has member which always lost. Also there always exist one number in B which would have lost to a number in W.

So this contradict our assumption and hence there always exist such a number in w

2. Show that there is an input so that if a member u ∈ L is compared to a number not in L, u looses.

Now lets consider that u wins when compared with number not in L.

u can't win with number in W as number of w always won. Also there always exist a number in L which would have lost to all number in B.

Hence this contradict our assumption and hence such a number exist.

3.

Show that when the algorithm stops, there is exactly one element in W , exactly one element in in L and the rest of the elements belong to B.

When algorithm stop, let there are two number in W. This means that these two numbers which were never compared otherwise one of them will not remain in w. So this can't happen and hence there will be only one number in W.

Similar argument holds for L.

Question 4 and 5 are not clear

4. Recall that n = |N |, w = |W |, ` = |L|, and consider 3n + 2w + 2`. Show that at
start the value is 3n and at the end at the end its 4

5. Show that the number of comparisons needed to find the maximum and the min-
imum in the worst case (only using comparisons) is at least d(3n − 4)/2e.