[Algo] Exercise 8.1

Exercise 8.1-1
What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
solution:
At least each element in $\langle a_1, a_2, \ldots , a_n\rangle$ has to be compared. Hence the smallest depth is n-1.

Exercise 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 technique from Section A.2.
solution:
Since  $\langle \lg k \rangle$ is an increasing sequence, we can evaluate the summation by integral
$$\int_{m-1}^n f(x)dx \leq \sum_{k = m}^n f(k) \leq \int_{m}^{n+1}f(x)dx.$$


Exercise 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$?
solution:
Suppose that there exists a comparison sort which sorts $m$ inputs of $n!$ permutations in linear time. Suppose that the height of the portion of the decision tree consisting of $m$ corresponding leaves is $h$. We have $m \leq 2^h$, which gives us $h \geq \lg m$. By Stirling's approximation:
$$n! = \sqrt{2\pi n}(\frac{n}{e})^n(1 + \Theta(\frac{1}{n})),$$
we have

Hence, for $m = n!/2, n!/n, n!/2^n$, $h = \Omega(n\lg n)$. It is impossible for a comparison sort whose running time is linear for $m =n!/2, n!/n, n!/2^n$ of the $n!$ inputs of length n.

Exercise 8.1-4
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 of 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. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
solution:
There are only $(k!)^{n/k}$ reachable leaves in such decision tree. Suppose that the height of the decision tree is $h$. We have $2^h \geq (k!)^{n/k}$, which gives us $h \geq (n/k)\lg(k!) \geq (n/k)(k\lg k - k\lg e) = n\lg k - n\lg e = \Omega(n\lg k)$.