chap lower bounds better than sorting the list is this true for the second biggest valuefor the median valuein later sections we will examine those questions for this sectionwe will continue our examination of lower bounds proofs by reconsidering the simple problem of finding the maximum value in an unsorted list lower bounds on other selection problems will be covered in later sections of this here is simple algorithm for finding the largest value /return position of largest value in "astatic int largest(int[aint currlarge /holds largest element position for (int = < lengthi++/for each element if ( [currlargea[ ]/if [iis larger currlarge /remember its position return currlarge/return largest position obviously this algorithm requires comparisons is this optimalit should be intuitively obvious that it isbut let us try to prove it (before reading further you might try writing down your own proof proof the winner must compare against all other elementsso there must be comparisons this proof is clearly wrongbecause the winner does not need to explicitly compare against all other elements to be recognized for examplea standard singleelimination playoff sports tournament requires only comparisonsand the winner does not play every opponent so let' try again proof only the winner does not lose there are losers single comparison generates (at mostone (newloser thereforethere must be comparisons this proof is sound howeverit will be useful later to abstract this by introducing the concept of posets as we did in section we can view the maximumfinding problem as starting with poset where there are no known relationshipsso every member of the collection is in its own separate dag of one element proof to find the largest valuewe start with poset of dags each with single elementand we must build poset having all elements in one dag such that there is one maximum value (and by implicationn loserswe wish to connect the elements of the poset into single dag with the minimum number of links this requires at least links comparison provides at most one new link thusa minimum of comparisons must be made what is the average cost of largestbecause it always does the same number of comparisonsclearly it must cost comparisons we can also consider