# How does Knuth measure the running time of this program?

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.

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.

• See here for an explanation of the method. – Raphael Jul 13 '15 at 8:56

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).