Skip to content

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$?

If the sort runs in linear time for $m$ input permutations, then the height $h$ of the portion of the decision tree consisting of the $m$ corresponding leaves and their ancestors is linear.

Use the same argument as in the proof of Theorem 8.1 to show that this is impossible for $m = n! / 2$, $n! / n$, or $n! / 2^n$.

We have $2^h \ge m$, which gives us $h \ge \lg m$. For all the possible m's given here, $\lg m = \Omega(n\lg n)$, hence $h = \Omega(n\lg n)$.

In particular,

$$ \begin{aligned} \lg \frac{n!}{2} & = \lg n! - 1 \ge n\lg n - n\lg e - 1, \\ \lg \frac{n!}{n} & = \lg n! - \lg n \ge n\lg n - n\lg e - \lg n, \\ \lg \frac{n!}{2^n} & = \lg n! - n \ge n\lg n - n\lg e - n. \\ \end{aligned} $$

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.)

Let $S$ be a sequence of $n$ elements divided into $n / k$ subsequences each of length $k$ where all of the elements in any subsequence are larger than all of the elements of a preceding subsequence and smaller than all of the elements of a succeeding subsequence.

Claim

Any comparison-based sorting algorithm to sort $s$ must take $\Omega(n\lg k)$ time in the worst case.

Proof

First notice that, as pointed out in the hint, we cannot prove the lower bound by multiplying together the lower bounds for sorting each subsequence. That would only prove that there is no faster algorithm that sorts the subsequences independently. This was not what we are asked to prove; we cannot introduce any extra assumptions.

Now, consider the decision tree of height $h$ for any comparison sort for $S$. Since the elements of each subsequence can be in any order, any of the $k!$ permutations correspond to the final sorted order of a subsequence. And, since there are $n / k$ such subsequences, each of which can be in any order, there are $(k!)^{n / k}$ permutations of $S$ that could correspond to the sorting of some input order. Thus, any decision tree for sorting $S$ must have at least $(k!)^{n / k}$ leaves. Since a binary tree of height $h$ has no more than $2^h$ leaves, we must have $2^h \ge (k!)^{n / k}$ or $h \ge \lg((k!)^{n / k})$. We therefore obtain

$$ \begin{aligned} h & = \lg((k!)^{n / k}) \\ & = (n / k)\lg(k!) \\ & \ge (n / k)\lg((k/k)^{k / 2}) \\ & = (n / 2)\lg(k / 2). \end{aligned} $$

The third line comes from $k!$ having its $k / 2$ largest terms being at least $k / 2$ each. (We implicitly assume here that $k$ is even. We could adjust with floors and ceilings if $k$ were odd.)

Since there exists at least one path in any decision tree for sorting $S$ that has length at least $(n / 2)\lg(k / 2)$, the worst-case running time of any comparison-based sorting algorithm for $S$ is $\Omega(n\lg k)$.