View Feed
group-icon
Coffee Room
Discuss anything here - everything that you wish to discuss with fellow engineers.
12940 Members
Join this group to post and comment.
Alok mishra
Alok mishra • Oct 19, 2013

How nested loops affect programs' execution ?

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 .
rahul69
rahul69 • Oct 19, 2013
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
Anoop Kumar • Oct 19, 2013
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
Jeffrey Arulraj • Oct 21, 2013
@ianoop 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
Alok mishra • Oct 22, 2013
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
Anoop Kumar • Oct 22, 2013
Yes, 1st one is more efficient. I asked because whenever looping , be precise how many iteration it gonna take.
Alok mishra
Alok mishra • Oct 22, 2013
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
Anoop Kumar • Oct 22, 2013
Even Nested loop is not favorable. More than one nested loop is quite a overhead.
KenJackson
KenJackson • Oct 26, 2013
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.

Share this content on your social channels -