c++loopsfor-loop

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?


Solution

  • 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.