algorithmloopsanalysisoperations

How many primitive operations in a simple loop?


I have a bunch of code to find the primitive operations for. The thing is that there aren't really many detailed resources out on the web on the subject. In this loop:

for i:=0 to n do
  print test
end

How many steps do we really have? In my first guess I would say n+1 considering n for the times looping and 1 for the print. Then I thought that maybe I am not precise enough. Isn't there an operation even to add 1 to i in every loop? In that matter we have n+n+1=2n+1. Is that correct?


Solution

  • The loop can be broken down into its "primitive operations" by re-casting it as a while:

    int i = 0;
    while (i < n)
    {
        print test;
        i = i + 1;
    }
    

    Or, more explicitly:

    loop:
        if (i < n) goto done
        print test
        i = i + 1
        goto loop
    done:
    

    You can then see that for each iteration, there is a comparison, an increment, and a goto. That's just the loop overhead. You'd have to add to that whatever work is done in the loop. If the print is considered a "primitive operation," then you have:

    Now, how that all gets converted to machine code is highly dependent on the compiler, the runtime library, the operating system, and the target hardware. And perhaps other things.