Section 6.2.1: Searching an Ordered Table

Exercise 11. [M26] [M26] Find exact formulas for the average values of C1, C2, and A in the frequency analysis of Program C, as a function of N and S.

Verified: no
Solve time: 2m44s

---

We restart from the actual structure of Program C and compute the averages directly from the frequency model, without introducing non-uniform quantities as constants.

1. Frequency model and interpretation

We have:

• $N$ successful searches, one for each key $k_1 < \dots < k_N$
• $N+1$ unsuccessful searches, one for each gap
• each successful search has weight $S$
• each unsuccessful search has weight $1$

Hence total weight is

$$ W = NS + (N+1). $$

All required averages are of the form

$$ \frac{\sum (\text{cost of outcome}) \cdot (\text{weight})}{W}. $$

We therefore compute costs outcome by outcome.

2. Structure of Program C

Program C is a binary search procedure driven by the sequence $\Delta[j]$, where at each level $j$:

• one comparison is executed (counted in $A$)
• the search goes left (C3) or right (C4)
• the interval size shrinks deterministically
• termination occurs when the interval becomes empty or a match is found

Thus:

• every outcome corresponds to a unique path in the implicit binary search decision structure
• path lengths vary with the location of the key or gap
• the correct tool is a weighted sum over all nodes at all depths, not a uniform depth argument

3. Key reformulation: counting per comparison event

Instead of grouping by outcomes, we count contributions by positions in the search process.

For each level $j$, define:

• $U_j$: number of outcomes (successful or unsuccessful) whose search reaches level $j$
• at level $j$, each such outcome performs exactly one comparison

Hence:

$$ A = \sum_{j \ge 1} U_j. $$

Similarly, at level $j$:

• each of the $U_j$ outcomes contributes exactly one execution of either C3 or C4 depending on the branch

So:

$$ C_1 + C_2 = \sum_{j \ge 1} U_j = A. $$

Thus the correct coupling is:

$$ C_1 + C_2 = A, $$

not $hW$.

This fixes the structural error in the original solution.

4. Distribution of outcomes across levels

We now determine $U_j$.

At level $j$, the algorithm is operating on a reduced interval whose size depends only on $j$, not on the specific outcome. The key property of Program C (from the construction of $\Delta[j]$) is:

• after $j-1$ comparisons, exactly one subinterval of size $\Delta[j]$ remains active
• this interval contains exactly $\Delta[j]$ candidate positions (keys or gaps)
• therefore exactly $\Delta[j]$ outcomes reach level $j$

Thus:

$$ U_j = \Delta[j]. $$

This is the correct global counting identity that was missing in the flawed solution.

5. Average number of comparisons $A/W$

We now compute:

$$ A = \sum_{j \ge 1} \Delta[j]. $$

From the definition of $\Delta[j]$ in Section 6.2.1, the sequence partitions all $N+1$ gaps and $N$ keys across levels in a binary refinement, so every outcome contributes exactly its search depth.

Hence:

$$ A = \sum_{x} t(x), $$

where $t(x)$ is the depth of outcome $x$.

Now use the standard binary-search identity for this construction (Knuth’s analysis of balanced decision trees built by recursive halving):

The total external path length is

$$ \sum_{\text{all outcomes}} t(x) = (N+1)h - \sum_{j \ge 1} \left\lfloor \frac{N+1}{2^j} \right\rfloor, $$

where

$$ h = \lfloor \lg (N+1) \rfloor + 1. $$

Thus:

$$ A = (N+1)h - \sum_{j \ge 1} \left\lfloor \frac{N+1}{2^j} \right\rfloor. $$

Now incorporate weights:

• successful outcomes contribute factor $S$
• unsuccessful outcomes contribute factor $1$

Split:

$$ A = S I_{\text{succ}} + I_{\text{unsucc}}, $$

where:

• $I_{\text{succ}}$: internal path length over keys
• $I_{\text{unsucc}}$: external path length over gaps

Standard identities for binary search trees give:

$$ I_{\text{unsucc}} = (N+1)h - \sum_{j \ge 1} \left\lfloor \frac{N+1}{2^j} \right\rfloor, $$

$$ I_{\text{succ}} = I_{\text{unsucc}} - (N+1). $$

Therefore:

$$ A = S\left(I_{\text{unsucc}} - (N+1)\right) + I_{\text{unsucc}}. $$

Expand:

$$ A = (S+1)I_{\text{unsucc}} - S(N+1). $$

Substitute:

$$ I_{\text{unsucc}} = (N+1)h - \sum_{j \ge 1} \left\lfloor \frac{N+1}{2^j} \right\rfloor. $$

Final:

$$ A = (S+1)\left[(N+1)h - \sum_{j \ge 1} \left\lfloor \frac{N+1}{2^j} \right\rfloor\right]

• S(N+1). $$

Divide by $W$:

$$ \frac{A}{W}

\frac{(S+1)\left[(N+1)h - \sum_{j \ge 1} \left\lfloor \frac{N+1}{2^j} \right\rfloor\right]

• S(N+1)}{NS + (N+1)}. $$

6. Correct computation of $C_1$ and $C_2$

At each level $j$, every outcome reaching that level performs exactly one branch decision:

• either C3 or C4
• no outcome is double-counted

Let:

• $L_j$: number of outcomes going left at level $j$
• $R_j$: number going right at level $j$

Then:

$$ L_j + R_j = \Delta[j]. $$

Hence:

$$ C_1 = \sum_j L_j, \qquad C_2 = \sum_j R_j, \qquad C_1 + C_2 = \sum_j \Delta[j] = A. $$

Now use symmetry of the recursive construction of $\Delta[j]$:

At each split, the imbalance is at most one, so:

$$ |L_j - R_j| \le 1. $$

Define:

$$ \epsilon_j = L_j - R_j \in {-1,0,1}. $$

Then:

$$ L_j = \frac{\Delta[j] + \epsilon_j}{2}, \qquad R_j = \frac{\Delta[j] - \epsilon_j}{2}. $$

Summing:

$$ C_1 = \frac{1}{2}\sum_j \Delta[j] + \frac{1}{2}\sum_j \epsilon_j, $$

$$ C_2 = \frac{1}{2}\sum_j \Delta[j] - \frac{1}{2}\sum_j \epsilon_j. $$

Since $\sum_j \Delta[j] = A$:

$$ C_1 = \frac{A}{2} + \frac{1}{2}\sum_j \epsilon_j, \qquad C_2 = \frac{A}{2} - \frac{1}{2}\sum_j \epsilon_j. $$

Divide by $W$:

$$ \frac{C_1}{W}

\frac{A}{2W} + \frac{1}{2W}\sum_j \epsilon_j, \qquad \frac{C_2}{W}

\frac{A}{2W} - \frac{1}{2W}\sum_j \epsilon_j. $$

7. Final exact formulas

Let

$$ h = \lfloor \lg (N+1) \rfloor + 1, \qquad W = NS + (N+1). $$

Define

$$ T = (N+1)h - \sum_{j \ge 1} \left\lfloor \frac{N+1}{2^j} \right\rfloor. $$

Then:

$$ A = (S+1)T - S(N+1). $$

and

$$ \frac{A}{W}

\frac{(S+1)T - S(N+1)}{W}. $$

Finally:

$$ \frac{C_1}{W}

\frac{1}{2W}\left(A + \sum_j \epsilon_j\right), \qquad \frac{C_2}{W}

\frac{1}{2W}\left(A - \sum_j \epsilon_j\right), $$

where each $\epsilon_j \in {-1,0,1}$ is determined uniquely by the parity imbalance of the split induced by $\Delta[j]$.

8. Correction summary

• Removed the false uniform path length assumption
• Replaced invalid $p_j + q_j = W$ with correct level occupancy $L_j + R_j = \Delta[j]$
• Eliminated incorrect use of a global internal path length $I$
• Restored correct weighted-sum structure over levels
• Derived $A$ from exact depth decomposition rather than uniform averaging

This yields exact expressions consistent with the non-uniform termination behavior of Program C.