Question

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

Answer 1

If the given algorithm employs m comparisons to determine 'x' that is the ith smallest element in a given sample of n elements. By tracing the m comparisons in the given log, the i -1 smaller elements can be determined by the theory of transitivity. Furthermore, If x > a and a > b, then x > b can be estimated without actually conducting a comparison between x and b. Similarly, the n - i larger elements can be found, too. It is uncertain that there is a possibility of x greater than a certain number or not by the comparison in the given log. It is not possible. Otherwise, the algorithm does not work correctly.

Step-by-step explanation:

If the given algorithm employs m comparisons to determine 'x' that is the ith smallest element in a given sample of n elements. By tracing the m comparisons in the given log, the i -1 smaller elements can be determined by the theory of transitivity. It is uncertain that there is a possibility of x greater than a certain number or not by the comparison in the given log.