sorting theorem any comparison-based algorithm to find the median must use at least  / (log ncomparisons proof apply theorem with  / the lower bound for selection is not tightnor is it the best knownsee the references for details adversary lower bounds although decision-tree arguments allowed us to show lower bounds for sorting and some selection problemsgenerally the bounds that result are not that tightand sometimes are trivial for instanceconsider the problem of finding the minimum item since there are possible choices for the minimumthe information theory lower bound that is produced by decision-tree argument is only log in theorem we were able to show the bound by using what is essentially an adversary argument in this sectionwe expand on this argument and use it to prove the following lower bound  / comparisons are necessary to find both the smallest and largest item recall our proof that any algorithm to find the smallest item requires at least comparisonsevery elementxexcept the smallest elementmust be involved in comparison with some other elementyin which is declared larger than otherwiseif there were two different elements that had not been declared larger than any other elementsthen either could be the smallest this is the underlying idea of an adversary argument which has some basic steps establish that some basic amount of information must be obtained by any algorithm that solves problem in each step of the algorithmthe adversary will maintain an input that is consistent with all the answers that have been provided by the algorithm thus far argue that with insufficient stepsthere are multiple consistent inputs that would provide different answers to the algorithmhencethe algorithm has not done enough stepsbecause if the algorithm were to provide an answer at that pointthe adversary would be able to show an input for which the answer is wrong to see how this workswe will re-prove the lower bound for finding the smallest element using this proof template theorem (restatedany comparison-based algorithm to find the smallest element must use at least comparisons