new proof begin by marking each item as (for unknownwhen an item is declared larger than another itemwe will change its marking to (for eliminatedthis change represents one unit of information initially each unknown item has value of but there have been no comparisonsso this ordering is consistent with prior answers comparison between two items is either between two unknowns or it involves at least one item eliminated from being the minimum figure shows how our adversary will construct the input valuesbased on the questioning if the comparison is between two unknownsthe first is declared the smaller and the second is automatically eliminatedproviding one unit of information we then assign it (irrevocablya number larger than the most convenient is the number of eliminated items if comparison is between an eliminated number and an unknownthe eliminated number (which is larger than by the prior sentencewill be declared largerand there will be no changesno eliminationsand no information obtained if two eliminated numbers are comparedthen they will be differentand consistent answer can be providedagain with no changesand no information provided at the endwe need to obtain - units of informationand each comparison provides only unit at the mosthenceat least comparisons are necessary lower bound for finding the minimum and maximum we can use this same technique to establish lower bound for finding both the minimum and maximum item observe that all but one item must be eliminated from being the smallestand all but one item must be eliminated from being the largestthus the total information that any algorithm must acquire is howevera comparison eliminates both from being the maximum and from being the minimumthusa comparison can provide two units of information consequentlythis argument yields only the trivial lower bound our adversary needs to do more work to ensure that it does not give out two units of information more than it needs to to achieve thiseach item will initially be unmarked if it "winsa comparison ( it is declared larger than some item)it obtains if it "losesa comparison ( it is declared smaller than some item)it obtains an at the endall but two items will be wl our adversary will ensure that it only hands out two units of information if it is comparing two unmarked items that can happen only / timesthen the remaining information has to be obtained one unit at timewhich will establish the bound answer information new new < no change mark as change to #elim consistently no change no change all others figure adversary constructs input for finding the minimum as algorithm runs