6
$\begingroup$

I'm reading "Structured Programming with go to Statements" by Knuth, and in it, he gives the following algorithm and a run-time cost analysis of some hypothetically generated code, letting $n$ stand for the number of times around the loop, and where instruction fetch and memory accesses cost one unit, so for example $r2\gets m$ costs two units because it's an instruction fetch, and you need to fetch $m$ from memory.

enter image description here

enter image description here

My question is what does $a$ mean in these equations? How can the instructions associated with the not found label execute more than once, rather than $a$ times? Given the nondeterminism of whether you'll execute the not found instructions depending on the contents of $A$, I can expect there's a special way of dealing with it in the analysis, but I don't follow him in the paper where he claims the total running time based on this analysis is $6n+10$. He says (+ 3 if not found), implying that $a$ is $1/2$, but using that assumption, the total sum comes out to $6n+8.5$, (+3 if not found). Is this some common notation I'm missing? No where in the paper is $a$ defined.

$\endgroup$
  • 1
    $\begingroup$ See here for an explanation of the method. $\endgroup$ – Raphael Jul 13 '15 at 8:56
2
$\begingroup$

Knuth's $a$ is not standard notation. Here it's just a flag which is $0$ if the element was found and $1$ if it wasn't found. When I sum the elements in his table I get $6n + 10 + 3a$, so it's $6n + 10$ if the element is found and $6n + 13$ if it's not found (which is $3$ more).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.