sec state space lower bounds proofs initial state of the algorithm is ( and the end state is ( thusevery run for any algorithm must go from state ( to state ( we also observe that once an element is identified to be middleit can then be ignored because it can neither be the minimum nor the maximum given that there are four types of elementsthere are types of comparison comparing with middle cannot be more efficient than other comparisonsso we should ignore thoseleaving six comparisons of interest we can enumerate the effects of each comparison type as follows if we are in state (ijkland we have comparisonthen the state changes are as follows : : : : or : or : or ( ( ( ( ( ( ( ( (ij jj jjjjj kk kkk kkk ll ll ll ll nowlet us consider what an adversary will do for the various comparisons the adversary will make sure that each comparison does the least possible amount of work in taking the algorithm toward the goal state for examplecomparing winner to loser is of no value because the worst case result is always to learn nothing new (the winner remains winner and the loser remains loserthusonly the following five transitions are of interestu : : : : : ( ( ( ( (ij jj jk kk kk llll only the last two transition types increase the number of middlesso there must be of these the number of untested elements must go to and the first transition is the most efficient way to do this thusdn/ of these are required our conclusion is that the minimum possible number of transitions (comparisonsis dn/ thusour algorithm is optimal