Thursday, July 16, 2015

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

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts