How nested loops affect programs' execution ?

Replies

• 

  rahul69

  Alok mishra

  As i was asked to write a program to generate all possible anagram for a given word , the logic that has struck my mind at first was using nested loops but i didnt care about execution time and complexity . So i want to be clear if nested loops affect programs' execution badly .

  It depends on the no of times the loop runs, and the amount of nesting,(of course not considering hardware related factors) and if both these parameters are large, it really affects the execution time badly.
• 

  Anoop Kumar

  Yes, Loops add complexity and execution time very badly specially nested loops. They should be avoided as much as possible, using collections (Data structure containers).
  Here complexity is Cyclomatic complexity, which is in one line - Number of independent paths in programs.
  
  Loops/nested doesn't much add in complexity but performance is degraded to worse. while nested looping you must consider what data you want and when to break the loop.
  
  See the following code, do you find any execution difference between them? which one you will go?
  
  

  for(int i = 0; i < l.length; i++) {
      for(int j = 0; j <= i; j++) {
          //your code
      }
  }
  
  
  and :
  
  for(int i = 0; i < l.length; i++) {
      for(int j = 0; j < l.length; j++) {
          //your code
      }
  }

• 

  Jeffrey Arulraj

  @#-Link-Snipped-# the first snippet seems better coded for me is that the correct
  
  Cos I am reducing iterations in the inner loop.
  
  But based on the need don't you think it will vary a lot
• 

  Alok mishra

  ianoop

  Yes, Loops add complexity and execution time very badly specially nested loops. They should be avoided as much as possible, using collections (Data structure containers).
  Here complexity is Cyclomatic complexity, which is in one line - Number of independent paths in programs.
  
  Loops/nested doesn't much add in complexity but performance is degraded to worse. while nested looping you must consider what data you want and when to break the loop.
  
  See the following code, do you find any execution difference between them? which one you will go?

  the first one !! but why did you ask this ?
• 

  Anoop Kumar

  Yes, 1st one is more efficient. I asked because whenever looping , be precise how many iteration it gonna take.
• 

  Alok mishra

  ianoop

  Yes, Loops add complexity and execution time very badly specially nested loops. They should be avoided as much as possible, using collections (Data structure containers).

  the first one !!
  

  ianoop

  Yes, 1st one is more efficient. I asked because whenever looping , be precise how many iteration it gonna take.

  if i say i am using 8 nested loops in a program , does it sound impractical (not correct word) or what would you suggest about that ?
• 

  Anoop Kumar

  Even Nested loop is not favorable. More than one nested loop is quite a overhead.
• 

  KenJackson

  If you're comparing every combination of 8 characters using all 26 letters by brute force, you'll have to make 26^8 or 2.09E11 comparisons. That's 209 billion inner loops.
  
  A different approach might be to only compare the words that appear in some dictionary, for example the file /usr/share/dict/words which is probably distributed with every distro of Linux and many other OSes. My copy has 479,828 words--one word per line. (Coincidentally, that's roughtly the square root of 26^8.)
  
  So comparing every line in that file would result in a single loop with a tiny fraction of the total comparisons.