Problem with calculate complexity

[Dani90]

Hello ....I have problem with calculate complexity for second loop

 f=1;
x=3;
for (int i = 1; i <= n; i*=2) 
   for (int j = 1; j <= i * i; j++) 
      if (i % j == 0) 
      for (int k = 1; k <= j; k++) 
         f=f*x;

[tpb]

The code raises 3 to the power given by the number of times the f *= x line executes, which is the number of times the k loop iterates.

i goes through powers of two. So j % i is true only when j is a power of 2 that is <= i. And, in that case, j gives the number of times that the k loop will iterate. We want the total number of times that the k loop iterates, in terms of n.

Here's a table for some values of n (missing values are the same as the previous power of two).

n   number of k-loop iterations (KLI)
1   1        =  1
2   1+2      =  3
4   1+2+4    =  7
8   1+2+4+8  = 15

It seems that KLI = 2**(n/2) - 1
where ** is exponentiation and / is integer division

So the code raises 3 to that power, and the power is the complexity.


BTW, the fact that j goes up to the square of i is pointless since anything above i itself will not satisfy i % j == 0. So the algorithm (such as it is) is perhaps better written:

    for (int i = 1; i <= n; i *= 2) 
       for (int j = 1; j <= i; j *= 2) 
          for (int k = 1; k <= j; k++)
             f *= x;

[jonnin]

hmm.

the 2nd loop viewed as a stand-alone item (ignore the outer loop) will execute whatever is inside of it a constant number of times, since i is a constant in this context so i*i is also a constant in this context. That means its O(n). I consider the modulo and comparison part of the work, even though its a condition, so that means the loop, to me, does O(N) amount of work.

if you consider the outer loop as part of the evaluation, i becomes a variable, and its log based.
the informal answer is probably O(2^n) due to the rapid domination of the inner loop term. Let me explain...
say n is "only" 64. the outer loop executs 7 times, I think. The inner loop executes off squares, so it goes 1, then 4, then 16, then 64, ... 4096. If you only look at the dominating term, 4096 is so much larger than its previous go (1024) that it may as well only consider the last term. So the dominating term is 2 to the N power inner loop executions.

if you need it more precisely, its some function times 2 to a power, but big O thankfully glosses over that.

Hopefully I did that right. Someone check me?
-- Nice, someone did, and he also got 2 to a power. He did the sum of the KLIs better; I thought it would be a multiplier but I missed that. /shrug

[Ganado]

I do not believe it's exponential complexity, but it's been a while since I've done this.

Can someone tell me what they think the run-time complexity of this set of loops should be, given n?

We all know that

for (int i = 0; i < n; i++)
  for (int j = 0; j < i; j++)
    // ... 

becomes O(n^2) because it ends up being "sum i from 1 to n" number of iterations, which is (n)(n-1), which simplifies to n^2, but:

for (int i = 0; i < log(n); i++)
  for (int j = 0; j < i; j++)
    // ... 

Can anyone tell me what the complexity of that is (assuming the inner operation is O(1), of course)? Note, I'm not hijacking the thread, I'm trying to solve OP's problem but am getting caught up on some details.

[icy1]

@Ganado outer loop log(n), inner loop log(n-1). Inner loop is effectively same as log(n). So we have O( (log(n))² )

Similarly, it looks like OP's is log(n), then log(n)log(n), then ... not sure exactly but feels like another log(n)? O( (log(n))⁴ ) ?

[Ganado]

@icy1

inner loop log(n-1)

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:

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:

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:

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.

[icy1]

consider the simpler

#include <iostream>

using namespace std;

int main() 
{
    int count = 0;
    int n = 6;

    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=i; ++j)
        {
            count++;
            cout << "i: "<<i<<", j: "<<j<<".  count: "<<count<<endl;
        }        
    }    
    cout << count << endl;  //21
}

n=4, count=10
n=5, count=15
n=6, count=21
n=7, count=28

These are numbers on Pascal's triangle, and sums from 1..n.

Also, related to the triangle in position 2 from the left --

5! / (2!3!) = 10
6! / (2!4!) = 15
7! / (2!5!) = 21
8! / (2!6!) = 28

There's something similar for when j<i (depends on if you count the outer loop skipping inner as an iteration)