Which loop is faster? | PROGRAMMING INTERVIEWS

Which loop is faster? | PROGRAMMING INTERVIEWS

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.

1. The SECOND executes assignment operations ( j = 0 or i = 0) 101 times while FIRST executes only 11 times.
2. The SECOND does 101 + 1100 comparisons (i < 100 or j < 10) while the FIRST does 11 + 1010 comparisons (i < 10 or j < 100).
3. 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.

Read full article from Which loop is faster? | PROGRAMMING INTERVIEWS