## thedarklord Newbie Poster

Please can you help me to calc the complexity of this algorithm it may looks easy but i am new to all that

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

## mike_2000_17 2,669

Calculating the complexity of an algorithm is really just a matter of figuring out how many times an operation will be done.

If you take the outer loop, `for(int i = 1; i <= n; i *= 2)`, you can ask yourself how many iterations will be executed. If n = 8, then you'll iterations i = (1,2,4,8). If n = 5, then i = (1,2,4). If n = 13, then i = (1,2,4,8). You get the idea? The number of iterations will be the log in base 2 of n, or just log(n).

You can proceed like this for the inner loops, each time you must multiply the results.

For loops that have inter-dependent bounds, like `for(int j = 1; j <= i * i; j++)`, where the bound of the inner-loop is dependent on the value of the outer-loop, you can simply take the upper bound of the outer loop and assume some constant factor. That is, in that loop, the upper-bound is `i * i` where `i` is at most `n`, so you can consider the upper-bound of that inner-loop to be a constant factor times n squared, as in `C * n * n`, and since we don't care about the constant factor, you can just say that it is `O(n^2)`.

I'll let you figure out the rest, since I get the feeling this might be a homework question.

commented: Ok thanks for you help +0
commented: :) +8

## thedarklord

Thanks for your help agine and i want to make sure that the inner loop for (int k = 1; k <= ji; k++)
the complexity for it is from k=1 to j
i and i is at most n and j is at most n^2 so the complexity is from k=1 to n^3
right ?

## mike_2000_17 2,669

Yes. But there's a trap in the question. Pay attention to the if-statement:

``````if (j % i == 0)
``````
commented: I figured out that i is of base 2 like 2^l for example and th if statment is true when j is also of base 2 but in the inner is j*i so i don't know how to continue please help me +0

## thedarklord

I figured out that i is of base 2 like 2^l for example and th if statment is true when j is also of base 2 but in the inner is j*i so i don't know how to continue please help me

## mike_2000_17 2,669

If you look at these two lines:

``````for (int j = 1; j <= i * i; j++)
if (j % i == 0)
//..
``````

The if-statement means that the iteration will only execute if `j` is a multiple of `i`. So, in combination with the for-statement before it, how many multiples of `i` do you have between 1 and `i * i`? Obviously, there are only `i` multiples of `i` between 1 and `i * i`. So, the two lines are actually equivalent to this:

``````for (int j = i;   // the first multiple of i is i.
j <= i * i;  // the last multiple of i is i * i.
j += i)      // the next multiple of i is j + i.
//..
``````

Or, you could also write it as:

``````for (int l = 1; l <= i; l++) {
int j = l * i;
//..
};
``````

which actually executes on `i` times, obviously. And because `i` is bounded by `n`, the complexity of that loop (merging the original for-loop and if-statement) is O(n).

So, using the above, we can reduce the for-loops to this:

``````for (int i = 1; i <= n; i *= 2)           // O( log2(n) )
for (int j = 1; j <= i; j++)            // less-than O(n)
for (int k = 1; k <= j * i * i; k++)  // less-than O(n^3)
f=x*f;
``````

From this, it is pretty trivial to say that the rough upper-bound on the complexity is `O( log2(n) * n ^ 4 )`.

I say that this is a rough upper-bound because you can get a tighter upper-bound on the complexity by a more thorough analysis, especially, merging the outer-loop with the inner-loops (hint: because `i` progresses exponentially, the complexity of the first inner loop is considerably less than O(n)).

commented: Thank you very much, you helped me a lot +0