C++ behavior of for loops vs. while loops
- by kjh
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?
