yes < no tn ty tree ty tree figure smallest three elements are abc }largest four elements are defg }the comparison between and for this choice of and can be eliminated when forming tree tkth smallest form new decision treetby purging any comparisons in between an element in and an element in since any element in is smaller than an element in rthe comparison tree node and its right subtree may be removed from without any loss of information figure shows how nodes can be pruned any permutation of that is fed into tfollows the same path of nodes and leads to the same leaf as corresponding sequence consisting of permutation of followed by the same permutation of since identifies the overall kth smallest elementand the smallest element in is that elementit follows that tidentifies the smallest element in thus tmust have at least | |- leaves these leaves in directly leaves representing since there are correspond to choices for sk- there must be at least leaves in - direct application of lemma allows us to prove the lower bounds for finding the second smallest element and the median theorem any comparison-based algorithm to find the kth smallest element must use at least log comparisons - proof immediate from lemma and lemma theorem any comparison-based algorithm to find the second smallest element must use at least log comparisons proof applying theorem with yields log