sorting the lower bounds for all these problemswith the exception of finding the medianare tightalgorithms exist that use exactly the specified number of comparisons in all our proofswe assume all items are unique lemma if all the leaves in decision tree are at depth or higherthe decision tree must have at least leaves proof note that all nonleaf nodes in decision tree have two children the proof is by induction and follows lemma the first lower boundfor finding the smallest itemis the easiest and most trivial to show theorem any comparison-based algorithm to find the smallest element must use at least comparisons proof every 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 lemma the decision tree for finding the smallest of elements must have at least leaves proof by theorem all leaves in this decision tree are at depth or higher then this lemma follows from lemma the bound for selection is little more complicated and requires looking at the structure of the decision tree it will allow us to prove lower bounds for problems and on our list lemma the decision tree for finding the kth smallest of elements must have at least leaves - proof observe that any algorithm that correctly identifies the kth smallest element must be able to prove that all other elements are either larger than or smaller than otherwiseit would be giving the same answer regardless of whether was larger or smaller than tand the answer cannot be the same in both circumstances thus each leaf in the treein addition to representing the kth smallest elementalso represents the smallest items that have been identified let be the decision treeand consider two setss xk }representing the smallest itemsand which are the remaining itemsincluding the