chap lower bounds - - figure the poset that represents the minimum information necessary to determine the ith element in list we need to know which element has values less and values morebut we do not need to know the relationships among the elements with values less or greater than the ith element finding the ith best element we now tackle the problem of finding the ith best element in list as observed earlierone solution is to sort the list and simply look in the ith position howeverthis process provides considerably more information than we need the minimum amount of information that we actually need to know can be visualized as shown in figure that isall we need to know is the items less than our desired valueand the - items greater we do not care about the relative order within the upper and lower groups so can we find the required information faster than by first sortinglooking at the lower boundcan we tighten that beyond the trivial lower bound of comparisonswe will focus on the specific question of finding the median element ( the element with rank / )because the resulting algorithm can easily be modified to find the ith largest value for any looking at the quicksort algorithm might give us some insight into solving the median problem recall that quicksort works by selecting pivot valuepartitioning the array into those elements less than the pivot and those greater than the pivotand moving the pivot to its proper location in the array if the pivot is in position ithen we are done if notwe can solve the subproblem recursively by only considering one of the sublists that isif the pivot ends up in position ithen we simply solve by finding the ith best element in the left partition if the pivot is at position ithen we wish to find the kth element in the right partition what is the worst case cost of this algorithmas with quicksortwe get bad performance if the pivot is the first or last element in the array this would lead to possibly ( performance howeverif the pivot were to always cut the array in halfthen our cost would be modeled by the recurrence (nt( / or (ncost finding the average cost requires us to use recurrence with full historysimilar to the one we used to model the cost of quicksort if we do thiswe will find that (nis in (nin the average case