The worst-case performance of a randomized selection algorithm is O(n2). It is possible to improve the section of an element of the randomized selection algorithm to obtain a worst-case performance of O(n). We can obtain the performance of O(n) by using an algorithm, that is, deterministic selection.
Median of the median is an algorithm that provides us with the approximate median value, that is, a value close to the actual median for a given unsorted list of elements. This approximate median is often used as a pivot point in the quickselect algorithm for selecting the ith smallest element from a list. It is due to the fact that the median of median algorithm finds out the estimated median in a linear time, and when this estimated median is used as a pivot point in the quickselect algorithm, the worst-case running time's complexity drastically improves...
