9.3-4

Suppose that an algorithm uses only comparisons to find the i th smallest element in a set of n elements. Show that it can also find the i - 1 smaller elements and the n - i larger elements without performing any additional comparisons.


Suppose that the algorithm uses m comparisons to find the ith smallest element x in a set of n elements. If we trace these m comparisons in the log, we can easily find the i - 1 smaller elements by transitivity. If x > a and a > b, then x > b can be deduced without actually performing a comparison between x and b. Similarly, the n - i larger elements can be found, too.

Say we can not decide that some element e is smaller or greater than x. Then we claim that the algorithm does not work properly, since an adversary could design an input in which e is the ith largest element instead of x. The i -1 and n -i smaller elements may be not in sorted order with respect to each but they are in sorted order with respect to the ith smallest element. What I mean we get i -1 and n-i smaller elements but it does'nt any thing about the relative order of the smaller or larger elements it means they are just smaller or larger than i.