theorem any sorting algorithm that uses only comparisons between elements requires at least log( !)comparisons in the worst case proof decision tree to sort elements must have nleaves the theorem follows from the preceding lemma theorem any sorting algorithm that uses only comparisons between elements requires ( log ncomparisons proof from the previous theoremlog( !comparisons are required log( !log( ( )( ( )( )log log( log( log log >log log( log( log( / >log >log ( log nthis type of lower-bound argumentwhen used to prove worst-case resultis sometimes known as an information-theoretic lower bound the general theorem says that if there are different possible cases to distinguishand the questions are of the form yes/nothen log pquestions are always required in some case by any algorithm to solve the problem it is possible to prove similar result for the average-case running time of any comparison-based sorting algorithm this result is implied by the following lemmawhich is left as an exerciseany binary tree with leaves has an average depth of at least log decision-tree lower bounds for selection problems section employed decision-tree argument to show the fundamental lower bound that any comparison-based sorting algorithm must use roughly log comparisons in this sectionwe show additional lower bounds for selection in an -element collectionspecifically comparisons are necessary to find the smallest item log comparisons are necessary to find the two smallest items  / (log ncomparisons are necessary to find the median