The selection is a problem of finding the Kth smallest key in array L which is containing n keys. It can be solved in general by sorting L. In that case, sorting requires O(n log₂n) key comparisions. In this paper we establish a lower bound of O(n) ...
The selection is a problem of finding the Kth smallest key in array L which is containing n keys. It can be solved in general by sorting L. In that case, sorting requires O(n log₂n) key comparisions. In this paper we establish a lower bound of O(n) for selection problem using adversary argument in the worst case.