Which loop is faster?

Question: A very basic programming puzzle is being asked in programming interviews since last few years. Which of the below two loops will run faster?

/* FIRST */
for(i=0;i<10;i++)
 for(j=0;j<100;j++)
     //do somthing

/* SECOND */
for(i=0;i<100;i++)
 for(j=0;j<10;j++)
     //do somthing

Answer: Firstly it seems, that since the code body (//do something) will run 1000 times in both the cases and so both loops should take equal time. But if we have a closer look how the loop statements are executing then we can certainly deduce that first loop is faster.

The SECOND executes assignment operations ( j = 0 or i = 0) 101 times while FIRST executes only 11 times.
The SECOND does 101 + 1100 comparisons (i < 100 or j < 10) while the FIRST does 11 + 1010 comparisons (i < 10 or j < 100).
The SECOND executes 1100 increment operations (i++ or j++) while the FIRST executes 1010 increment operation.

Points 1 and 2 can be verified from following code. It clearly shows the number of assignment and increment operations.

main()
{
 int i, j, k, l;
 l = 0;
 /* FIRST */
 for(i=0, l++, k=0;i<10;i++, k++)
     for(j=0, l++;j<100;j++, k++);
         printf("First Loop: %d\t%d\n", k, l);

 l= 0; 
 /* SECOND */
 for(i=0, l++, k=0;i<100;i++, k++)
     for(j=0,l++;j<10;j++, k++);
         printf("Second Loop: %d\t%d\n", k, l);
}

Output of above code is as follows:

First Loop: 1010 11
Second Loop: 1100 101

From the above output, we can clearly see that 2nd loops has more operations (assignment, increment). On a deeper analysis, comparison operations are also more in 2nd loop. So FIRST loop is clearly faster than SECOND.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.