Problem 3 - Algorithm

Regarding a comparison of two elements as an unit operation in inserting $n$ random elements to a binary tree, which is initially empty, we are interested in estimating the average number of comparisons.

1.

Derive the average number of comparisons when $n=3,4$.

2.

Show that the average number of comparisons is $0(\log n)$ for general $n$.

1.

$n=3$

$$\begin{tabular}{ccc} Sequence & Number of comparisons & Sum \\ ... ... 0+1+2 & 3 \\ 3 2 1 & 0+1+2 & 3 \\ \hline & & Mean = 8/3 \\ \end{tabular}$$

$n=4$

$$\begin{tabular}{ccc} Sequence & Number of comparisons & Sum \\ ... ...3 & 6 \\ 4 3 2 1 & 0+1+2+3 & 6 \\ \hline & & Mean = 29/6 \\ \end{tabular}$$

2.

See [AHO83] for a detailed answer.