Calculate algorithm complexity

[thedarklord]

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;

thanks in advance

[mike_2000_17]

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.

[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 ji 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]

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

if (j % i == 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]

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)).