chap lower bounds in the hangman game examplethe adversary is imagined to hold dictionary of words of some selected length each time the player guesses letterthe adversary consults the dictionary and decides if more words will be eliminated by accepting the letter (and indicating which positions it holdsor saying that its not in the word the adversary can make any decision it choosesso long as at least one word in the dictionary is consistent with all of the decisions in this waythe adversary can hope to make the player guess as many letters as possible before explaining how the adversary plays role in our lower bounds prooffirst observe that at least values must lose at least once this requires at least compares in additionat least values must lose to the second largest value that isk direct losers to the winner must be compared there must be at least comparisons the question ishow low can we make kcall the strength of element [ithe number of elements that [iis (known to bebigger than if [ihas strength aand [jhas strength bthen the winner has strength what strategy by the adversary would cause the algorithm to learn the least from any given comparisonit should minimize the rate at which any element improves it strength it can do this by making the element with the greater strength win at every comparison this is "fairuse of an adversary in that it represents the results of providing worst-case input for that given algorithm to minimize the effects of worst-case behaviorthe algorithm' best strategy is to maximize the minimum improvement in strength by balancing the strengths of any two competitors from the algorithm' point of viewthe best outcome is that an element doubles in strength this happens whenever bwhere and are the strengths of the two elements being compared all strengths begin at zeroso the winner must make at least comparisons when - < thusthere must be at least dlog ne comparisons our algorithm is optimal state space lower bounds proofs we now consider the problem of finding both the minimum and the maximum from an (unsortedlist of values this might be useful if we want to know the range of collection of values to be plottedfor the purpose of drawing the plot' scales of course we could find them independently in comparisons slight modification is to find the maximum in comparisonsremove it from the listand then find the minimum in further comparisons for total of comparisons can we do better than thisbefore continuingthink moment about how this problem of finding the minimum and the maximum compares to the problem of the last sectionthat of finding the second biggest value (and by implicationthe maximumwhich of these two