8.1 Lower bounds for sorting

8.1-1

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

For a permutation $a_1 \le a_2 \le \ldots \le a_n$, there are $n - 1$ pairs of relative ordering, thus the smallest possible depth is $n - 1$.

8.1-2

Obtain asymptotically tight bounds on $\lg(n!)$ without using Stirling's approximation. Instead, evaluate the summation $\sum_{k = 1}^n\lg k$ using techniques from Section A.2.

$$ \begin{aligned} \sum_{k = 1}^n\lg k & \le \sum_{k = 1}^n\lg n \\ & = n\lg n. \end{aligned} $$

$$ \begin{aligned} \sum_{k = 1}^n\lg k & = \sum_{k = 2}^{n / 2} \lg k + \sum_{k = n / 2}^n\lg k \\ & \ge \sum_{k = 1}^{n / 2} 1 + \sum_{k = n / 2}^n\lg n / 2 \\ & = \frac{n}{2} + \frac{n}{2}(\lg n - 1) \\ & = \frac{n}{2}\lg n. \end{aligned} $$

8.1-3

Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1 / n$ of the inputs of length $n$? What about a fraction $1 / 2^n$?

Consider a decision tree of height $h$ with $r$ reachable leaves corresponding to a comparison sort on $n$ elements. From Theorem 8.1, We have $n! / 2 \le n! \le r \le 2^h$. By taking logarithms, we have

$$h \ge \lg (n! / 2) = \lg (n!) - 1 = \Theta (n\lg n) - 1 = \Theta (n\lg n).$$

From the equation above, there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.

Consider the $1/n$ of inputs of length $n$ condition. we have $(1/n)n! \le n! \le r \le 2^h$. By taking logarithms, we have

$$h \ge \lg (n! / n) = \lg (n!) - \lg n = \Theta (n\lg n) - \lg n = \Theta (n\lg n).$$

From the equation above, there is no comparison sort whose running time is linear for $1/n$ of the $n!$ inputs of length $n$.

Consider the $1 / 2^n$ of inputs of length $n$ condition. we have $(1/2^n)n! \le n! \le r \le 2^h$. By taking logarithms, we have

$$h \ge \lg (n! / 2^n) = \lg (n!) - n = \Theta (n\lg n) - n = \Theta (n\lg n).$$

From the equation above, there is no comparison sort whose running time is linear for $1/2^n$ of the $n!$ inputs of length $n$.

8.1-4

Suppose that you are given a sequence of $n$ elements to sort. The input sequence consists of $n / k$ subsequences, each containing $k$ elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length $n$ is to sort the $k$ elements in each of the $n / k$ subsequences. Show an $\Omega(n\lg k)$ lower bound on the number of comparisons needed to solve this variant of the sorting problem. ($\textit{Hint:}$ It is not rigorous to simply combine the lower bounds for the individual subsequences.)

Assume that we need to construct a binary decision tree to represent comparisons. Since length of each subsequece is $k$, there are $(k!)^{n / k}$ possible output permutations. To compute the height $h$ of the decision tree, we must have $(k!)^{n / k} \le 2^h$. Taking logs on both sides, we know that

$$h \ge \frac{n}{k} \times \lg (k!) \ge \frac{n}{k} \times \left( \frac{k\ln k - k}{\ln 2} \right) = \frac{n\ln k - n}{\ln 2} = \Omega (n\lg k).$$