How to calculate the number of operations that occur during the execution of a for loop?

Question

I had an exam a couple of days ago and today the Instructor gave us the key answer of the exam.

One of the questions was

for ( j = 9; j >= 1; j-- )

Count the Number of operations

The result was 20.

Can anyone explain how he gets 20 operations from that?

Answer 1

Well, in the first iteration, j is set to 9. After that, each iteration basically executes the same two instructions:

• first, test whether j >= 1, and
• second, decrement j (j--).

This is done nine times (from 9 inclusively to 0 inclusively). In the very last iteration, we test again whether j >= 1 and since this is false, we exit the loop. We therefore get 1 + 9 * 2 + 1 = 20 iterations.

Answer 2

What value did you write down? Just curious.

Let's count them together, maya:

for (j = 9; j >= 1; j--)

one for assigning 9 to j = 1; one comparison of the current value of j to 1 for each iteration of the loop = 10; one decrement of j for each iteration of the loop except the last one = 9;

1 + 10 + 9 = 20 in my book.

Answer 3

You have 1 assignment (j=9). The "j--" operation will be run 9 times; the conditional check "j>=1" will be run 10 times (every iteration you ask the question "is j>=1"), the last will fail. So you have 1 + 9 + 10 = 20.

Your instructor is very, very bad if he is so mean as to not offer to help. This is one of those questions you either get or don't. The instructor should help. :)

Answer 4

20 operations:

set j = 9
check if j(9) >= 1
set j to 8
check if j(8) >= 1
set j to 7
check if j(7) >= 1
set j to 6
check if j(6) >= 1
set j to 5
check if j(5) >= 1
set j to 4
check if j(4) >= 1
set j to 3
check if j(3) >= 1
set j to 2
check if j(2) >= 1
set j to 1
check if j(1)>=1
set j to 0
check if j(0)>=1

for( j=n ; j>=0 ; j-- )

Ok, you start with two operations:

• (j=n)
• check (j>=0).

For all n<0 it stops there.

If n=0, you get an aditional:

• j--
• check (j>=0).

For n=1, you get another set of those.

So the number of operations is 2 for n<0 and 2n+4 for n>=0.

These things are not that hard. You just need to think like a computer and carefully note any change to the state (set of variables).