views:

553

answers:

2

how do you setup minimum number of comparisons in general?

+5  A: 

To cite Donald Knuth (by way of Wikipedia, since I don't have my copy of TAOCP at the moment), the lower bound for the number of comparisons is six:

http://en.wikipedia.org/wiki/Selection%5Falgorithm (scroll down to the section entitled "Lower Bounds").

Your goal is, effectively, to find the k lowest values where k is half the size of the list, rounded up, (so, k = 3; n = 5) and then take the max of those. Plugging that into the formula there on the page, you get:

(5 - 3) + 1 + 1 + 2 = 6

In this case, the actual minimum number of required comparisons is also six.

If you're in doubt that the task of finding the median is as hard as finding k lowest values, you may refer to Knuth's TAoCP, volume 3, excercise #2 after 5.3.3 chapter.

James McNellis
However, it's not obvious that finding N/2 lowest elements would be as hard as finding only one median.
Pavel Shved
Once you've found the N/2 smallest elements, the largest of those elements is the median, and since you've just done all of the necessary comparisons, you know which of the N/2 smallest elements is the largest.
James McNellis
Thanks for the TAoCP reference, Pavel.
James McNellis
Agreed. 6 is the best you can do .
+2  A: 
jk