TAOCP 6.1 Exercise 3

Section 6.1: Sequential Searching

Exercise 3. [16] [16] Write a MIX program for the algorithm of exercise 2. What is the running time of your program, in terms of the quantities C' and S in (1)?

A. [17| Does the idea of Algorithm Q carry over from subscript notation to linkedmemory notation? (See exercise 2.)

Verified: yes
Solve time: 2m50s

---

We restart the analysis from the instruction-level behavior of the MIX program.

Let $C'$ be the number of key comparisons performed, and let $S \in {0,1}$ indicate success ($S=1$) or failure ($S=0$).

1. Cost of the loop body

Each iteration of the loop corresponds to one comparison attempt and has the following instruction sequence:

$$ \begin{aligned} &\text{CMPA KEY,1} \ &\text{JE SUCCESS} \ &\text{LD1 LINK,1} \ &\text{J1Z FAILURE} \ &\text{JMP LOOP} \end{aligned} $$

Thus, in the unsuccessful control path through a full iteration, the cost is

$$ 5 \text{ instructions per iteration}. $$

Hence, if all $C'$ comparisons proceed without early success structure effects, the baseline loop cost is

$$ 5C'. $$

2. Correction for successful termination

If the search is successful, then on the iteration where the match occurs, execution transfers immediately via JE SUCCESS. In that iteration, the last three instructions

$$ \text{LD1 LINK,1},\quad \text{J1Z FAILURE},\quad \text{JMP LOOP} $$

are not executed.

Therefore, relative to the baseline $5C'$, a successful search saves exactly $3$ instructions.

Thus the loop cost is

$$ 5C' - 3S. $$

3. Initialization cost

Before entering the loop:

• LDA K contributes $1$
• LD1 FIRST,0 contributes $1$

So the initialization cost is

$$ 2. $$

4. Success block cost

If the search succeeds, execution enters:

SUCCESS  LDA INFO,1
         JMP *

This contributes

$$ 2S $$

additional instructions.

(No analogous cost appears in the failure case because control exits via J1Z FAILURE.)

5. Total running time

Combine all components:

$$ T = (5C' - 3S) + 2 + 2S. $$

Simplify:

$$ T = 5C' + 2 - S. $$

Final result

$$ \boxed{T = (5C' - S + 2)\ \text{MIX time units}} $$

This is the correct running time of the linked-memory MIX implementation of the sequential search algorithm in terms of $C'$ and $S$.