chap lower bounds bounds on searching in listsboth those that are unordered and those that are ordered section deals with finding the maximum value in listand presents model for selection based on building partially ordered set section presents the concept of an adversarial lower bounds proof section illustrates the concept of state space lower bound section presents linear time worst-case algorithm for finding the ith biggest element on list section continues our discussion of sorting with quest for the algorithm that requires the absolute fewest number of comparisons needed to sort list introduction to lower bounds proofs the lower bound for the problem is the tightest (highestlower bound that we can prove for all possible algorithms that solve the problem this can be difficult bargiven that we cannot possibly know all algorithms for any problembecause there are theoretically an infinite number howeverwe can often recognize simple lower bound based on the amount of input that must be examined for examplewe can argue that the lower bound for any algorithm to find the maximum-valued element in an unsorted list must be ohm(nbecause any algorithm must examine all of the inputs to be sure that it actually finds the maximum value in the case of maximum findingthe fact that we know of simple algorithm that runs in (ntimecombined with the fact that any algorithm needs ohm(ntimeis significant because our upper and lower bounds meet (within constant factor)we know that we do have "goodalgorithm for solving the problem it is possible that someone can develop an implementation that is "littlefaster than an existing oneby constant factor but we know that its not possible to develop one that is asymptotically better we must be careful about how we interpret this last statehowever the world is certainly better off for the invention of quicksorteven though mergesort was available at the time quicksort is not asymptotically faster than mergesortyet is not merely "tuningof mergesort either quicksort is substantially different approach to sorting so even when our upper and lower bounds for problem meetthere are still benefits to be gained from newclever algorithm so now we have an answer to the question "how do know if have good algorithm to solve problem?an algorithm is good (asymptotically speakingif its upper bound matches the problem' lower bound if they matchwe know to throughout this discussionit should be understood that any mention of bounds must specify what class of inputs are being considered do we mean the bound for the worst case inputthe average cost over all inputsregardless of which class of inputs we considerall of the issues raised apply equally