@icy1
I think you're correct, but can you explain this? How are you separating out the inner loop from the outer loop if the inner loop is dependent on the current state of the outer loop?
@tpb:
above i itself will not satisfy i % j == 0.the fact that j goes up to the square of i is pointless since anything above i itself will not satisfy i % j == 0. |
What do you mean by "pointless"? Do you mean the if statement existing doesn't change the complexity of the code? Because I think it does, but feel free to challenge that if you think otherwise. I'll demonstrate my reasoning below.
Note: The following is assuming OP is asking for the run-time complexity in big-Oh notation, dependent on the "n" variable, which is kept constant.
Well, without being too robust, if we look at the loops, let's start with the outer one.
• In the outer loop, you double
i each time, so this loop will end up running about log(n) times (the base of the log and any other constants don't matter).
• In the middle loop, you're going up to
i^2. But what can
i go up to? We said log(n), so you're actually going up to log(n)^2.
• In the inner loop, you're going from 1 to j
The if-statement actually seems to affect the complexity in a pretty fun way to figure out.
When i = 1, we have the only iteration evaluating to i % j == 0.
i = 1, j = 1, i % j == 0
When i = 4, we have i % j == 0 when:
1 2 3
|
i = 4, j = 1, i % j == 0
i = 4, j = 2, i % j == 0
i = 4, j = 4, i % j == 0
| |
When i = 32, we have i % j == 0 when:
1 2 3 4 5 6
|
i = 32, j = 1, i % j == 0
i = 32, j = 2, i % j == 0
i = 32, j = 4, i % j == 0
i = 32, j = 8, i % j == 0
i = 32, j = 16, i % j == 0
i = 32, j = 32, i % j == 0
| |
So let's see, when i = 64, we have i % j = 0 when:
1 2 3 4 5 6 7
|
i = 64, j = 1, i % j == 0
i = 64, j = 2, i % j == 0
i = 64, j = 4, i % j == 0
i = 64, j = 8, i % j == 0
i = 64, j = 16, i % j == 0
i = 64, j = 32, i % j == 0
i = 64, j = 64, i % j == 0
| |
We can see a pattern form, that the inner-most loop will only happen when j is a power of 2. That's important.
The inverse of this statement is that the inner-most loop will only happen log(j) times.