# Recurrence formula for optimal binary search tree

This question is from Section 15.5 of Introduction to Algorithms (third edition).

We are given sequence of keys, $$k = \{ k_{1},k_{2},\dots,k_{n} \}$$, where $$k_{1}.

For each key $$k_{i}$$, where $$1\leq i \leq n$$, we have a probability $$p_{i}$$ that a search will be for $$k_{i}$$.

We let the sequence $$d =\{ d_{0},d_{1},\dots,d_{n} \}$$, where $$d_{0}, be for values not in $$k$$.

For each key $$d_{i}$$, where $$0\leq i \leq n$$, we have a probability $$q_{i}$$ that a search will be for $$d_{i}$$.

The goal is to construct an optimal binary search tree.

Let us define $$e[i,j]$$ as the expected cost of searching an optimal binary search tree containing the keys $$k_{i},\dots,k_{j}$$.

Let $$w(i,j) = \sum_{l=i}^{j} p_{l} + \sum_{l=i-1}^{j} q_{l}$$.

The book gives the following equation as the recurrence formula for forming the optimal binary search tree: $$e[i,j] = \begin{cases} q_{i-1} & \text{if } j = i-1, \\ \displaystyle\min_{i\le r\le j} \{e[i,r-1]+r[r+1],j]+w(i,j)\} & \text{if } i \leq j. \end{cases}$$

This formula makes sense for $$i\leq j$$, but I don't understand the case $$j = i-1$$.

Why is $$e[i,i-1] = q_{i-1}$$?

• I don't know what $w(i,j)$ is, but it looks like for each $(i,j)$ you want to build an optimal tree containing keys $k_i, \ldots, k_j$ and searchable for $k_i,\ldots, k_j, d_{i-1}, \ldots, d_j$. You want to compute $\sum_{k \in k_i,\ldots, k_j, d_{i-1}, \ldots, d_j}P(\text{$k$is searched for}) \cdot \text{(the number of operations required to search for$k$in the tree)}$. When the tree is empty, the only key is $d_{i-1}$ with probability $q_{i-1}$, and we need $O(1)$ operations to find it.
– user114966
Oct 13 '20 at 23:03
• @Dmitry I added the definition of w(i,j) Oct 13 '20 at 23:48
• Introduction to Algorithms was written by 3 or 4 authors (depending on the edition). Oct 14 '20 at 7:15
• @YuvalFilmus I added the full book details Oct 14 '20 at 7:38

The easy case occurs when $$j = i-1$$. Then we have just the dummy key $$d_{i-1}$$. The expected search cost is $$e[i,i-1] = q_{i-1}$$.
In slightly more detail, $$e[i,j]$$ is supposed to be the cost of the optimal binary search tree for $$k_i,\ldots,k_j$$. It is important to understand what cost means here. The cost is with respect to the following distribution on the input:
• With probability $$p_i$$, key $$k_i$$ is being searched.
• With probability $$q_i$$, a dummy key $$d_i$$ between $$k_i$$ and $$k_{i+1}$$. (When $$i = 0$$, it is a key smaller than $$k_1$$, and when $$i = n$$, it is a key larger than $$k_n$$.)
Unfortunately, the textbook is being extremely sloppy, and never bothers to explain what they mean by "the cost of the optimal binary search tree for $$k_i,\ldots,k_j$$". It seems that they are measuring the expected cost with respect to the stated keys as well as with respect to the dummy keys $$d_{i-1},\ldots,d_j$$. That is, they want to minimize $$q_{i-1} \mathit{cost}(d_{i-1}) + p_i \mathit{cost}(k_i) + q_{i+1} \mathit{cost}(d_{i+1}) + \cdots + q_{j-1} \mathit{cost}(d_{j-1}) + p_j \mathit{cost}(k_j) + q_j \mathit{cost}(d_j).$$ When $$j = i-1$$, there are no real keys, but there is a dummy key $$d_{i-1} = d_j$$, and so the cost is $$q_{i-1} \mathit{cost}(d_{i-1})$$. The optimal cost here is clearly $$1$$, and that's how they get $$q_{i-1}$$.