What does this 'efficiency rating' mean by analysing assembly instructions?

One of my data structures and algorithms questions is to analyse assembly code and figure out the time complexity of it. I just don't understand the example my professor gave me.

It is to turn C code into assembly instructions using http://gcc.godbolt.org/

The C code is:

int main(void)
{
 int a[] = {11,-22,33}, length = 3, count = 0;

 for (int i = 0 ; i < length ; i++)
    if (a[i] > 5) 
       count++;
}

The assembly code is:

main:
    pushq   %rbp
    movq    %rsp, %rbp
    movl    $11, -32(%rbp)
    movl    $-22, -28(%rbp)
    movl    $33, -24(%rbp)
    movl    $3, -12(%rbp)
    movl    $0, -4(%rbp)
    movl    $0, -8(%rbp)
.L4:
    movl    -8(%rbp), %eax
    cmpl    -12(%rbp), %eax
    jge .L2
    movl    -8(%rbp), %eax
    cltq
    movl    -32(%rbp,%rax,4), %eax
    cmpl    $5, %eax
    jle .L3
    addl    $1, -4(%rbp)
    .L3:
    addl    $1, -8(%rbp)
    jmp .L4
.L2:
    movl    $0, %eax
    popq    %rbp
    ret

And his explanation is:

Best case: Number of Instructions = 2 + n + 3 + 3(n+1) + 5n + 0 + 2n + 3 = 11n + 11

Worst case: Replace 0 by n to get Number of Instructions = 12n + 11

His rough explanation is:

Because we both approximate and also ignore actual constants (eg 11*t0), it is easier to reason as follows. The loop is executed n times, and the loop contents takes constant time, so total time is O(n). Most of the time we only use a rough analysis, which can be justified by the detailed analysis.

I do not understand the explanation. Can someone explain this to me better?

Solution

If I understand your version of your professor's question correctly, he's trying to teach you the difference between algorithmic order of magnitude and exact execution time.

The exact execution time takes a lot of work to compute.

There is a loop that will have either 10 or 11 instructions, depending on the value of a test. Your best case is that no element of the array a[] is greater than 5 (so nothing has to be incremented); your worst case is that all the elements are greater than 5 (so they all have to be incremented).
There is the pre-loop setup, which takes 1 instruction per element in the array to initialize plus 5 more instructions. Including the extra instruction per element of the array takes the number of instructions per "loop" (really, instructions per element in the array) from [10 or 11] to [11 or 12].
There are the first three instructions of the loop, which perform the loop test and will be executed one time more than the rest of the loop; this makes the extra execution of the instructions overhead, even though they're included in the count of instructions in the loop.
There are the post-loop instructions, 3 more overhead instructions.

When you add them all up, you get your best and worse case equations: 11n + 11 is 11 instructions per array element + 11 overhead; 12n + 11 is 12 instructions per array element + 11 overhead.

On the algorithmic order of magnitude, the code is extremely predictable, so it's easy to compute. Because there are no breaks or multiple passes per input datum, it takes one loop per array element, O(n). If (say) it compared every element to every other element and therefore had to have an inner loop of n elements and an outer loop of n elements, that would be O(n^2). Simple sort routines tend to be like that.

What I believe is the core of the lesson, is the realization that computing exact time of execution is HARD. This little example didn't take into account things like how fast your memory bus is, whether your test data fit into the processor's cache, and a dozen other possible things that could affect the time of execution. Understanding the general order of magnitude is easy by comparison (though on complex algorithms, it can still be hard). And usually the order is all you need. On the rare occasions that you need the detailed analysis, you now understand how to do it... but the rough analysis is good enough for almost anything you'll need to do.

In the normal world of professional development, only specialists generally need to care about instruction-by-instruction timing. Understanding the order of algorithms will let you compare your ideas on a higher level, and get to the right answer in a much more reasonable time.

Hope this helps!