exercises_12.4.md

12.4 Randomly built binary search trees

12.4-1

Prove equation (12.3).

$$\displaystyle \sum_{i=0}^{n-1} \binom{i+3}{3} = \binom{n+3}{4}$$.

$$ \begin{array}{rll} \displaystyle \sum_{i=0}^{n-1} \binom{i+3}{3} &=& \displaystyle \sum_{i=0}^{n-1} \frac{(i+3)(i+2)(i+1)}{6} \\ &=& \displaystyle \frac{1}{6} \sum_{i=0}^{n-1} i^3 + 6i^2 + 11i + 6 \\ &=& \displaystyle \frac{1}{6} \left ( \frac{(n-1)^2 n^2}{4} + \frac{6(n-1)n(2n-1)}{6} + \frac{11n(n-1)}{2} + 6n \right ) \\ &=& \displaystyle \frac{n(n+1)(n+2)(n+3)}{24} \\ &=& \displaystyle \binom{n+3}{4} \end{array} $$

12.4-2

Describe a binary search tree on n nodes such that the average depth of a node in the tree is $$\Theta(\lg n)$$ but the height of the tree is $$\omega(\lg n)$$. Give an asymptotic upper bound on the height of an $$n$$-node binary search tree in which the average depth of a node is $$\Theta(\lg n)$$.

$$\Theta(\sqrt{n \lg n})$$

12.4-3

Show that the notion of a randomly chosen binary search tree on $$n$$ keys, where each binary search tree of $$n$$ keys is equally likely to be chosen, is different from the notion of a randomly built binary search tree given in this section.

For $$n=3$$, there are 5 binary search trees. However, if we build the trees will a random permutation, the first tree will built twice.

12.4-4

Show that the function $$f(x) = 2^x$$ is convex.

$$ \begin{array}{rll} \displaystyle f(x) + f(y) - 2f \left ( \frac{x + y}{2} \right ) &=& \displaystyle 2^x + 2^y - 2 \cdot 2^{(x + y)/2} \\ &=& \displaystyle (2^{x/2})^2 + (2^{y/2})^2 - 2 \cdot 2^{x/2} \cdot 2^{y/2} \\ &=& \displaystyle (2^{x/2} - 2^{y/2})^2 \ge 0 \end{array} $$

Therefore $$f(x) = 2^x$$ is convex.

12.4-5 $$\star$$

Consider RANDOMIZED-QUICKSORT operating on a sequence of $$n$$ distinct input numbers. Prove that for any constant $$k > 0$$, all but $$O(1/n^k)$$ of the $$n!$$ input permutations yield an $$O(n\lg n)$$ running time.

$$\dots$$