CODEWITHSUNDEEP
c++loopsfor-loop
kjh
kjh

Reputation: 3403

C++ behavior of for loops vs. while loops

As far as I understand, when you write a for-loop similar to this one

for (int i = 0; i < SOME_NUM; i++) { 
  if (true)
    do_something();
  else
    do_something_else();
}

The time complexity of this operation is mostly affected by the if (true) statement because the for-loop iterations don't actually involve any comparisons of i to SOME_NUM, the compiler will just essentially run the code inside the for-loop SOME_NUM times. Please correct me if I am wrong.

However if this is correct, then how do the following nested for-loops behave?

for (int i = 0; i < SOME_NUM; i++) {
  for (int j = 0; j < i; j++) {
   do_something();
  } 
}

The j in the inner for-loop is now upper bound by i, a value that changes every time the loop restarts. How will the compiler compile this? Do these nested for-loops essentially behave like a for-loop with while-loop inside of it? If you're writing an algorithm that uses nested for-loops where the inner counting variable depends on the outer counting variable should you be concerned about what this will do to the complexity of your algorithm?

Upvotes: 0

Views: 521

Answers (3)

haccks
haccks

Reputation: 106012

The time complexity of this operation is mostly affected by the if (true) statement because the for-loop iterations don't actually involve any comparisons of i to SOME_NUM, the compiler will just essentially run the code inside the for-loop SOME_NUM times. Please correct me if I am wrong.

Yes you are wrong. At the beginning of each iteration i is incremented and the conditional expression i < SOME_NUM is checked.

If you're writing an algorithm that uses nested for-loops where the inner counting variable depends on the outer counting variable should you be concerned about what this will do to the complexity of your algorithm?

Yes. In this case you have to consider the effect of nesting. So, better you should have to remove the nesting.

Upvotes: 1

Rakib
Rakib

Reputation: 7625

I guess you should learn basic loop constructs. A loop construct has a conditional statement which dictates if the loop will be entered and how many times will iterate. The if(true) simply dictates whether the following statement(s) will be executed or not (in this case it will be since condition is always true).

In summary, the first loop will be executed SUM_NUM times ( O(SUM_NUM)), and second loop is a O(n^2) loop.

Upvotes: 1

John3136
John3136

Reputation: 29266

"Please correct me if I am wrong."

You are wrong.

You can add i++ in your "first" loop somewhere and that would "break" your code. Of course a comparison of i to SOME_NUM is performed.

Upvotes: 3

Related Questions