Chapter 8.1

Consider a graph \(G = (V, E)\), which \(V\) represents the set of all \(n\) elements, and \(E\) represents the set of all comparison, then we should connect graph \(G\) for a comparison sort, at we need at least \(n - 1\) edges, thus the smallest possible depth of a leaf in a decision tree for a comparison sort is \(n - 1\).

For example, we do comparisons between \(a_i\) and \(a_{i+1}\) for \(i \in [1, n - 1]\), when \(a_1 \leq a_2 \leq a_3 \leq ... \leq a_{n-1} \leq a_n\).

Since \(\lg k\) is monotonically increasing, we can approximate the summation use the formula \(A.11\).

\begin{align*} \int_{0}^{n}\lg(x)dx \leq \sum_{k=1}^{n}\lg k \leq \int_{1}^{n+1}\lg(x)dx \end{align*}

Evaluate the integral, we have

\begin{align*} \frac{n(\lg n-1)}{\ln 2} \leq \sum_{k=1}^{n}\lg k \leq \frac{(n+1)(\lg(n+1)-1)}{\ln 2} \end{align*}

From the inequation, we obtain the asymptotically tight bounds \(\Theta(n\lg n)\).

Assume the running time is at most \(cn\), we know that there are at most \(2^{cn+1}\) leaves under depth \(cn\).

Since \(2^{cn+1} = o(\frac{1}{2}n!)\), there is no comparison sort whose running time is linear for at least half of the \(n!\) inputs of length \(n\).

Since \(2^{cn+1} = o(\frac{1}{n}n!)\), there is no comparison sort whose running time is linear for at a fraction of \(1/n\) of the \(n!\) inputs of length \(n\).

Since \(2^{cn+1} = o(\frac{1}{2^n}n!)\), there is no comparison sort whose running time is linear for at a fraction of \(1/2^n\) of the \(n!\) inputs of length \(n\).

Build a decision tree to represent a comparison sort of the given problem, assume the number of leaves is \(l\) and the height of the tree is \(h\), we know that

\begin{align*} (k!)^{\frac{n}{k}} \leq l \leq 2^h \end{align*}

Take logarithms on the inequation, we have

\begin{align*} h &\geq \frac{n}{k}\lg(k!)\\ &=\Omega(n\lg k) \end{align*}

Thus the lower bound of the number of comparisons is \(\Omega(n\lg k)\).