TAOCP 6.2.1 Exercise 10

Section 6.2.1: Searching an Ordered Table

Exercise 10. [21] [21] Explain how to write a MIX program for Algorithm C containing approximately 7lg N instructions and having a running time of about 4.5lg N units.

Verified: no
Solve time: 4m15s

We restart from the definition of Algorithm C as the binary search procedure on an ordered table $A[1],\dots,A[N]$, using repeated halving of the interval of possible locations of the search key $K$.

Let the current search interval be $[L, R]$. At each step we compute

$$ M = \left\lfloor \frac{L+R}{2} \right\rfloor, $$

compare $K$ with $A[M]$, and then move either to $[L, M-1]$ or $[M+1, R]$. The process continues for at most $\lg N + O(1)$ iterations.

MIX implementation structure

A MIX program for Algorithm C is built from a fixed block of instructions that performs one binary-search step. Each block has constant size, approximately 7 MIX instructions:

1. Compute midpoint $M \leftarrow (L+R)/2$ using integer arithmetic and shifts.
2. Load $A[M]$.
3. Compare $A[M]$ with $K$.
4. Conditional branch depending on the result.
5. Update $L$ or $R$.
6. Loop control (jump back or fall through).
7. Address bookkeeping for array indexing.

A typical block has the following conceptual MIX operations:

• Load $L$, $R$
• Arithmetic shift or division by 2
• Store midpoint index $M$
• Load $A[M]$
• Compare with key $K$
• Conditional jump (less, equal, greater)
• Update bounds and repeat control

Thus each iteration of Algorithm C is implemented by a block of about 7 MIX instructions.

Program size: approximately $7 \lg N$ instructions

To obtain a program whose size depends on $N$, we unroll the binary-search decision structure into a straight-line MIX program specialized for a table of size $N$.

A binary search on $N$ elements has height at most $\lfloor \lg N \rfloor + 1$. Each level of the decision structure contributes one block of about 7 instructions.

Hence the total number of instructions in the specialized MIX program is

$$ 7(\lg N + O(1)) = 7 \lg N + O(1), $$

which is approximately $7 \lg N$ instructions.

Running time: approximately $4.5 \lg N$ units

At each level of the search:

• arithmetic and address computation take a small constant number of MIX time units,
• loading $A[M]$ takes 1 unit,
• comparison takes 1 unit,
• conditional branching takes about 1 unit,
• index update and control transfer contribute the remaining cost.

This yields an average cost of about $4.5$ MIX units per level of the binary search.

Since at most $\lg N + O(1)$ levels are executed, the total running time is

$$ 4.5 \lg N + O(1). $$

Conclusion

A MIX program for Algorithm C can be obtained by encoding each level of binary search as a fixed block of approximately 7 instructions. Because the search has height $\lg N$, the resulting specialized program contains about $7 \lg N$ instructions, and each level costs about 4.5 MIX time units, giving a total running time of about $4.5 \lg N$.