Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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.

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.

Asked By : Isaac Block

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

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback