Exercise 8.1-1

What is the smallest possible depth of a leaf in a decision tree for a comparison sort?

This leaf represents the best case in which we perform the least number of comparisons to determine a proper sort order. For an input sequence of \(n\) elements, the best case requires \(n-1\) comparisons. Thus a decision tree’s leaves would have depths of at at least \(n-1\) which correspond to this best case.