# Upper bound on the average path length in binary search tree

I have been reading the chapter 6.2.2 in Knuth's book about lower and upper bound on the average path length in binary search tree. And I have problems with understanding small details of Theorem M (page 445, second edition) about an upper bound on the average cost of the search.

Here is the theorem:

Given $n$ keys and the probabilities of successful searches of keys ($p_1, \dots, p_n$) and probabilities of unsuccessful searches ($q_0, \dots, q_{n+1})$. Let $p_1 + \dots + p_n + q_0 + \dots + q_n = 1$, $P = p_1 + \dots + p_n$, $H = H(p_1, \dots, p_n, q_0, \dots, q_n).$ And let $C$ is the cost of the optimal binary search tree. Then $C \le H + 2 - P$.

Proof: Consider the following $n + 1$ sums: $s_0 = \frac{1}{2}q_0, s_1 = q_0 + p_1 + \frac{1}{2}q_1, s_2 = q_0 + p_1 + q_1 + p_2 + \frac{1}{2}q_2, \dots, s_n = q_0 + p_1 + \dots + q_{n-1} + p_n + \frac{1}{2}q_n$.

Then consider the binary representation of these sums. Let $\sigma_k$ be the leading bits of $s_k$, retaining just enough bits to distinguish $s_k$ from any $s_j, j \not= k$. Also, if $\sigma_{k-1}$ has form $\alpha_{k}0\beta$ and $\sigma_k$ has the form $\alpha_k1\gamma_k$ for some $\alpha_k, \beta_k, \gamma_k$.

Then Knuth shows how to build a tree using this binary representation. I skip this part since my question concerns only some inequalities.

The cost of an average search in the constructed tree is $\sum_{i=1}^{n}p_i(1 + |\alpha_i|) + \sum_{i=0}^{n}q_i|\sigma_i|$. Now the idea is to give an upper bound for this cost.

First of all, $p_k \le \frac{1}{2}q_{k-1} + p_k + \frac{1}{2}q_k = s_k - s_{k-1} \le 2^{|-\alpha_k|}$ since $s_k \le (.\alpha_k)_2 + 2^{-|\alpha_k|}$ and $s_{k-1} \ge (.\alpha_k)_2$. Moreover if $q_k \ge 2^{-t}$ then $s_k \ge s_{k-1} + 2^{-t - 1}$ and $s_{k+1} \ge s_k + 2^{-t - 1}$, hence $|\sigma| \le t + 1$. And it follows that $q_k < 2^{-|\sigma_k|+2}$.

I have problems with the two last inequalities. First I don't understand why do we need the variable $t$. And why $q_k$ is strictly less than $2^{|\sigma_k|+2}$. For me it's easier to say that $\max(|\alpha_k|, |\alpha_{k+1}|) = |\sigma_k| - 1$. Then since $2^{-\max(|\alpha_k|, |\alpha_{k+1}|)} \ge \min(s_k-s_{k-1}, s_{k+1} - s_k) \ge \frac{1}{2}q_k$, we have $q_k \le 2^{-|\sigma_k|+2}$.

Could you please explain why Knuth uses the variable $t$ and why first he shows that $|\sigma_k| \le t+1$ and only then $q_k < 2^{-|\sigma_k| + 2}$. Thank you.

• Knuth found it easier to express the proof this way. Perhaps he would have written it in some other way if he did it again. The Art of Computer Programming may be the "Programmer's Bible", but there is no need to apply methods of biblical exegesis when reading it. – Yuval Filmus Aug 7 '18 at 23:14
• My problem is here that the parameter $t$ is completely unnecessary here. – rbtrht Aug 8 '18 at 15:44
• In order to show that $q_k < 2^{-|\sigma_k|+2}$, we assume that $q_k \geq 2^{-|\sigma_k|+2}$ and deduce a contradiction. So $t = |\sigma_k|-2$. Knuth uses $t$ since it is shorter, and also as a matter of style – his argument derives the value $|\sigma_k|-2$. – Yuval Filmus Aug 9 '18 at 2:25