8-1 Probabilistic lower bounds on comparison sorting

In this problem, we prove a probabilistic $\Omega(n\lg n)$ lower bound on the running time of any deterministic or randomized comparison sort on $n$ distinct input elements. We begin by examining a deterministic comparison sort $A$ with decision tree $T_A$. We assume that every permutation of $A$'s inputs is equally likely.

a. Suppose that each leaf of $T_A$ is labeled with the probability that it is reached given a random input. Prove that exactly $n!$ leaves are labeled $1 / n!$ and that the rest are labeled $0$.

b. Let $D(T)$ denote the external path length of a decision tree $T$; that is, $D(T)$ is the sum of the depths of all the leaves of $T$. Let $T$ be a decision tree with $k > 1$ leaves, and let $LT$ and $RT$ be the left and right subtrees of $T$. Show that $D(T) = D(LT) + D(RT)+k$.

c. Let $d(k)$ be the minimum value of $D(T)$ over all decision trees $T$ with $k > 1$ leaves. Show that $d(k) = \min _{1 \le i \le k - 1} \{ d(i) + d(k - i) + k \}$. ($\textit{Hint:}$ Consider a decision tree $T$ with $k$ leaves that achieves the minimum. Let $i_0$ be the number of leaves in $LT$ and $k - i_0$ the number of leaves in $RT$.)

d. Prove that for a given value of $k > 1$ and $i$ in the range $1 \le i \le k - 1$, the function $i\lg i + (k - i) \lg(k - i)$ is minimized at $i = k / 2$. Conclude that $d(k) = \Omega(k\lg k)$.

e. Prove that $D(T_A) = \Omega(n!\lg(n!))$, and conclude that the average-case time to sort $n$ elements is $\Omega(n\lg n)$.

Now, consider a randomized comparison sort $B$. We can extend the decision-tree model to handle randomization by incorporating two kinds of nodes: ordinary comparison nodes and "randomization" nodes. A randomization node models a random choice of the form $\text{RANDOM}(1, r)$ made by algorithm $B$; the node has $r$ children, each of which is equally likely to be chosen during an execution of the algorithm.

f. Show that for any randomized comparison sort $B$, there exists a deterministic comparison sort $A$ whose expected number of comparisons is no more than those made by $B$.

a. There are $n!$ possible permutations of the input array because the input elements are all distinct. Since each is equally likely, the distribution is uniformly supported on this set. So, each occurs with probability $\frac{1}{n!}$ and corresponds to a different leaf because the program needs to be able to distinguish between them.

b. The depths of particular elements of $LT$ or $RT$ are all one less than their depths when considered elements of $T$. In particular, this is true for the leaves of the two subtrees. Also, $\{LT, RT\}$ form a partition of all the leaves of $T$. Therefore, if we let $L(T)$ denote the leaves of $T$,

$$\begin{aligned} D(T) & = \sum_{\ell \in L(T)} D_T(\ell) \\ & = \sum_{\ell \in L(LT)} D_T(\ell) + \sum_{\ell \in L(RT)} D_T(\ell) \\ & = \sum_{\ell \in L(LT)} (D_{LT}(\ell) + 1) + \sum_{\ell \in L(RT)} (D_{RT}(\ell) + 1) \\ & = \sum_{\ell \in L(LT)} D_{LT}(\ell) + \sum_{\ell \in L(RT)} D_{RT}(\ell) + k \\ & = D(LT) + D(RT) + k. \end{aligned}$$

c. Suppose we have a $T$ with $k$ leaves so that $D(T) = d(k)$. Let $i_0$ be the number of leaves in $LT$. Then, $d(k) = D(T) = D(LT) + D(RT) + k$. However, we can pick $LT$ and $RT$ to minimize the external path length.

d. We treat $i$ as a continuous variable, and take a derivative to find critical points. The given expression has the following as a derivative with respect to $i$

$$\frac{1}{\ln 2} + \lg i + \frac{1}{\ln 2} - \lg(k - i) = \frac{2}{\ln 2} + \lg\left(\frac{i}{k - i}\right),$$

which is $0$ when we have $\frac{i}{k - i} = 2^{-\frac{2}{\ln 2}} = 2^{-\lg e^2} = e^{-2}$. Therefore, $(1 + e^{-2})i = k$, $i = \frac{k}{1 + e^{-2}}$.

Since we are picking the two subtrees to be roughly equal size, the total depth will be order $\lg k$, with each level contributing $k$, so the total external path length is at least $k\lg k$.

e. Since before we that a tree with $k$ leaves needs to have external length $k\lg k$, and that a sorting tree needs at least $n!$ trees, a sorting tree must have external tree length at least $n!\lg (n!)$. Since the average case run time is the depth of a leaf weighted by the probability of that leaf being the one that occurs, we have that the run time is at least $\frac{n!\lg (n!)}{n!} = \lg (n!) \in \Omega(n\lg n)$.

f. Since the expected runtime is the average over all possible results from the random bits, if every possible fixing of the randomness resulted in a higher runtime, the average would have to be higher as well.