figure method for finding pivot for partitioning list that guarantees at least fixed fraction of the list will be in each partition we divide the list into groups of five elementsand find the median for each group we then recursively find the median of these / medians the median of five elements is guaranteed to have at least two in each partition the median of three medians from collection of elements is guaranteed to have at least five elements in each partition is it possible to modify our algorithm to get worst-case linear timeto do thiswe need to pick pivot that is guaranteed to discard fixed fraction of the elements we cannot just choose pivot at randombecause doing so will not meet this guarantee the ideal situation would be if we could pick the median value for the pivot each time but that is essentially the same problem that we are trying to solve to begin with noticehoweverthat if we choose any constant cand then if we pick the median from sample of size /cthen we can guarantee that we will discard at least / elements figure illustrates this idea this observation leads directly to the following algorithm choose the / medians for groups of five elements from the list choosing the median of five items can be done in constant time recursivelyselect mthe median of the / medians-of-fives partition the list into those elements larger and smaller than while selecting the median in this way is guaranteed to eliminate fraction of the elementswe still need to be sure that our recursion yields linear-time algorithm we model the algorithm by the following recurrence ( < (dn/ et( ( )/ dn/ we will prove that this recurrence is linear by assuming that it is true for some constant rand then show that ( <rn for all greater than some bound