TAOCP 6.2.1 Exercise 4

**Step 1: Average time of Program 6.

taocpmathematicsalgorithmsvolume-3medium

Section 6.2.1: Searching an Ordered Table

Exercise 4. [20] If a search using Program 6.1S (sequential search) takes exactly 638 units of time, how long does it take with Program B (binary search)?

Verified: no
Solve time: 7m13s

Solution

Step 1: Average time of Program 6.1S (sequential search).
Program 6.1S from Section 6.1 is

01 START ENT1 N           1
02 1H   CMPA KEY,1       N+1
03      JE  SUCCESS       A
04      DEC1 1            N
05      J1P 1H            N
06      JMP FAILURE       1-A

Using the standard MIX timings (ENT1, DEC1, J1P not taken = 1u; CMPA = 2u; JE, J1P taken = 2u; JMP = 1u), a successful search that finds the key on the (c)-th comparison ((1 \le c \le N)) takes

[ 1 + 2c + (c-1)\cdot1 + 2 + (c-1)\cdot1 + (c-1)\cdot2 = 6c - 1 \text{ units}. ]

Since all (N) keys are equally likely, the average number of comparisons is (\frac{N+1}{2}). Hence the average successful search time is

[ 6\cdot\frac{N+1}{2} - 1 = 3N + 2 \text{ units}. ]

Step 2: Determine (N) from the given time.
We are told that a search using Program 6.1S takes exactly 638 units. This must refer to the average successful search (the unsuccessful average (6N+1) never equals 638 for integer (N)). Thus

[ 3N + 2 = 638 \quad\Longrightarrow\quad N = 212. ]

Step 3: Average time of Program B (binary search).
Section 6.2.1 states that the average running time of Program B for a successful search is approximately (equation (5))

[ (18\lg N - 16),u, ]

where (\lg) denotes the binary logarithm.

Step 4: Compute the time for (N = 212).

[ \text{Time} = 18\lg 212 - 16. ]

Since (212 = 4 \times 53), (\lg 212 = 2 + \lg 53). Therefore

[ 18\lg 212 - 16 = 18(2 + \lg 53) - 16 = 20 + 18\lg 53. ]

Numerically, (\lg 53 \approx 5.727), giving

[ 20 + 18 \times 5.727 \approx 123.1 \text{ units}. ]

This completes the derivation.

[ \boxed{18\lg 212 - 16 ;\approx; 123.1\text{ units}} ]

∎