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;


## All 5 Replies

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

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 ?

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

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

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
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.