Nested Loop Iteration Count

Question

Sorry if I'm re-asking a previous question but I can't quite find a concrete answer to this question. How can I make a formula for nested for loop iterations besides basic ones like:

for (int i =0; i < N; i++)

I get the basic concept of count iterations of basic loops:

for (int i =0; i < N; i++)

The boolean condition is equal to some variable (for instance N) then is subtracted from the initial variable (for instance i) then is divided by the number of loops nested (in this case 1 since it is not nested). So the number of iterations for this loop would be:

(N - i) / 1

For example, for finding the iterations of nested loops this would be repeated down the loops until you make it to the innermost loop then you multiple all the loops for the iteration count.

I just don't understand more complicated loops with different increment conditions such as multiplication or division. Specifically how I can figure out how many times this loop iterates:

for (int i = 1; i < 1000; i *= 2)
    for (int j = 0; j < 1000; j++)

I know this has to do something with summation unfortunately I'm not seeing the connection. Any resources or advice would be greatly appreciated.

Answer 1

Just work out how many times each one loops. This is easy because they are not co-dependent (ie the j loop does not rely on i).

• The i loop goes 1, 2, 4, 8, 16, ..., 512. Since it must be less than 1000, it will stop when it reaches 1024. That's a total of 10 iterations. Count them by hand, or calculate log2(1024).

• The j loop goes 0, 1, 2, 3, ..., 999. That's a total of 1000 iterations.

So you have an inner loop of 1000 iterations that is repeated 10 times by the outer loop. That's a total of 10,000 iterations.

Answer 2

I think you're reading the loop syntax wrong?

Try reading them aloud, like this:

for this loop:

for (int i = 1; i < 1000; i *= 2)

The loop syntax reads:

Starting from One, keep looping while i is less than one thousand - and each time around the loop, multiply i by two.

So, i starts at one, and gets multiplied by two each time around the loop - i.e. 1, 2, 4, 8, 16.... This carries on until it gets to one thousand (or over it) - and the loop stops.

and for this loop:

for (int j = 0; j < 1000; j++)

the loop syntax says:

Starting at zero, keep looping while j is less than one thousand - and each time around the loop, add one to j.

For nested loops, there is no difference, except that for each time around the outer loop, the whole inner loop runs to completion.

I find that reading things aloud - or sounding them out in your head - can really help to make sense of them.