Chapter 12.4

To choose \(k\) elements from \(n\) elements, we could first choose one element, to be the largest of \(k\) elements, then we choose the remaining \(k-1\) elements, hence \(\binom{n}{k}=\sum_{i=1}^{n}\binom{i-1}{k-1}\). Thus, we have

\begin{align*} \binom{n+3}{4} &=\sum_{i=1}^{n+3}\binom{i-1}{3}\\ &=\sum_{i=4}^{n+3}\binom{i-1}{3}\\ &=\sum_{i=0}^{n-1}\binom{i+3}{3} \end{align*}

Consider a \(n\)-nodes binary search tree, with \(\sqrt{n}\) nodes to be a chain, and the other \(n-\sqrt{n}\) nodes to be asymptotically a complete binary search tree, then the average depth of a node in the tree is

\begin{align*} d(n) &=\frac{\sum_{i=1}^{\sqrt{n}}i+(n-\sqrt{n})\Theta(\lg(n-\sqrt{n}))}{n}\\ &=\Theta(\lg n) \end{align*}

and the height of the tree is \(h(n)=\sqrt{n}=\omega(\lg n)\).

When \(n=3\), the \(n! = 6\) inputs generate \(5\) different trees, which the inputs \(\langle 2,1,3 \rangle\) and \(\langle 2,3,1 \rangle\) generate the same tree. The probabilities are different from where each binary search tree of \(n\) keys is equally likely to be chosen.

We know that \(f(x)=2^x\) has a second derivative for \(x\in\mathbb{R}\), and \(f''(x) = 2^x\ln^2{2} > 0\), thus \(f(x)\) is strictly convex.

We could build a \(n\)-nodes binary search tree from performing QUICKSORT on \(n\) elements, by when we select a pivot, we make the pivot a new node and add it to that tree. Let \(h\) be the height of the tree, then we know the running time of QUICKSORT is \(O(nh)\). And for the \(n!\) input permutations, we have got a randomly built binary search tree on \(n\) keys.

We denote the height of a randomly built binary search tree on \(n\) keys by \(X_n\), then we have

\begin{align*} E[2^{X_n}] &\leq \frac{1}{4}\binom{n+3}{3} &\text{, from theorem 12.4}\\ &=O(n^3) \end{align*}

For any \(t > 0\), we have

\begin{align*} \Pr\{X_n\geq \lg t\} &=\Pr\{2^{X_n}\geq t\}\\ &\leq \frac{E[2^{X_n}]}{t} &\text{, Markov's inequality}\\ &=O(n^3t^{-1}) \end{align*}

Choose \(t=n^{k+3}\) for any \(k > 0\), we have

\begin{align*} \Pr\{X_n\geq (k+3)\lg n\} &=O(n^{-k}) \end{align*}

Thus for any constant \(k > 0\), all but \(O(1/n^k)\) of the \(n!\) input permutations yield an \(O(n\lg n)\) running time.