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

Question

Computers and Technology

Aileen Torres

19 October, 11:46

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

+1

Answers (1)

Know the Answer?

Alina Schwartz · 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.

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.