A Sorting Lower Bound
Date: 10/01/98 at 07:28:15 From: John Smither Subject: Lower Bound Proof Hi! I have the following university problem: Show that you cannot sort 3 elements with 2 comparisons. This is an example of lower bound. Can you help? Thanks, John
Date: 10/01/98 at 09:08:24 From: Doctor Rob Subject: Re: Lower Bound Proof There are six possible orders for the three numbers. Each comparison splits this set of orders into two sets, one of which agrees with the results, and one of which doesn't. Two comparisons will split the set of orders into four sets. At least one of these sets must contain at least two of the orders, by the Pigeonhole Principle. Those two cannot be distinguished by this procedure. You fill in the details and reasons. Here is another proof. If the two comparisons only involve two of the three elements, the second one is redundant, and the size of the third element relative to the first two will remain unknown. Thus the two comparisons must involve all three elements. Let the common element be a, and the first comparison a vs. b, the second a vs. c. No matter the results, the relative sizes of b and c will remain unknown, unless a is the middle element, which cannot be guaranteed ahead of time, and happens only part of the time at random. We cannot improve on this by comparing a vs. b, and then c vs. max(a,b), since if c is smaller than max(a,b), we will not be able to tell whether or not c is larger than min(a,b). Similarly, comparing c to min(a,b) won't work either. There is essentially nothing else to try. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.