Cheap and Secure Web Hosting Provider : See Now

# [Solved]: How does Knuth measure the running time of this program?

, ,
Problem Detail:

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.

#### Answered By : Yuval Filmus

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

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44358

3.2K people like this

#### Post a Comment

Let us know your responses and feedback