sorting < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < figure decision tree for three-element sort leaf in our casethis algorithm uses three comparisons in the worst case the average number of comparisons used is equal to the average depth of the leaves since decision tree is largeit follows that there must be some long paths to prove the lower boundsall that needs to be shown are some basic tree properties lemma let be binary tree of depth then has at most leaves proof the proof is by induction if then there is at most one leafso the basis is true otherwisewe have rootwhich cannot be leafand left and right subtreeeach of depth at most by the induction hypothesisthey can each have at most - leavesgiving total of at most leaves this proves the lemma lemma binary tree with leaves must have depth at least log lproof immediate from the preceding lemma