C++ behavior of for loops vs. while loops
Posted
by
kjh
on Stack Overflow
See other posts from Stack Overflow
or by kjh
Published on 2014-06-02T03:14:43Z
Indexed on
2014/06/02
3:26 UTC
Read the original article
Hit count: 608
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?
© Stack Overflow or respective owner