elements in the group we will let represent the huge elements these are elements that are known to be larger than large median similarlyt represents the tiny elementswhich are smaller than small median there are elements of type htwo are in each of the groups with an type medianand two elements are in the same group as similarlythere are elements of type elements of type or are guaranteed to be larger than vand elements of type or are guaranteed to be smaller than there are thus guaranteed to be large and small elements in our problem thereforea recursive call could be on at most elements let us extend this analysis to general of the form in this casethere are elements of type and elements of type there are elements of type hand also elements of type thusthere are elements that are guaranteed to be larger than and elements that are guaranteed to be smaller thusin this casethe recursive call can contain at most elements if is not of the form similar arguments can be made without affecting the basic result it remains to bound the running time to obtain the pivot element there are two basic steps we can find the median of five elements in constant time for instanceit is not hard to sort five elements in eight comparisons we must do this / timesso this step takes (ntime we must then compute the median of group of / elements the obvious way to do this is to sort the group and return the element in the middle but this takes on/ log / ( log ntimeso this does not work the solution is to call the selection algorithm recursively on the / elements this completes the description of the basic algorithm there are still some details that need to be filled in if an actual implementation is desired for instanceduplicates must be handled correctlyand the algorithm needs cutoff large enough to ensure that the recursive calls make progress there is quite large amount of overhead involvedand this algorithm is not practical at allso we will not describe any more of the details that need to be considered even sofrom theoretical standpointthe algorithm is major breakthroughbecauseas the following theorem showsthe running time is linear in the worst case theorem the running time of quickselect using median-of-median-of-five partitioning is (nproof the algorithm consists of two recursive calls of size and nplus linear extra work by theorem the running time is linear reducing the average number of comparisons divide and conquer can also be used to reduce the expected number of comparisons required by the selection algorithm let us look at concrete example suppose we have groupsof , numbers and are looking for the th smallest numberwhich we will call we choose subsetsof consisting of numbers we would expect that the value of is similar in size to the th smallest number in smore specificallythe fifth smallest number in sis almost certainly less than xand the th smallest number in sis almost certainly greater than