3. The following subroutine expects two parameters: p, the location of the first node, and k K, the key. After a successful search, it returns the location of the record found; otherwise, it returns zero.

01S3LDOUp,p,LINKCSS3. Advance. P LINK(P).
02:SearchBZp,0FCS + 1[1 – S]S4. End of file?
03LDOkp,p,KEYCkp KEY(P).
04CMPt,k,kpCS2. Compare.
05PBNZt,S3C[S]If K = KEY(P), terminate successfully.
060HPOP1,0Return p.    Image

The running time is (5C – 2S + 3)υ + (2CS)μ.

5. Program Q′ takes more time than Program Q if C < S + 2 + (CS) mod 2. A successful search (S = 1) will take more time only for ...

Get The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.