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
Output of above code is as follows:
/* 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
Solution:
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);
}
{
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 11From 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.
Second Loop: 1100 101
No comments:
Post a Comment