Calculating algorithm complexity of 1 2 4 8 pattern

Question

I need to calculate the complexity of this algorithm :

f=1;
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;

I figured out the pattern and the summation of the inner loop which is i^2(i(i+1)/2) but I can't get the summation of this pattern along the series of (1 2 4 8 16 ...)

So, how can I find the summation of this series?

Answer 1

I'm not going to solve this for you (this looks like homework). But here is a hint to simplify the problem.

This code:

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

is equivalent to this code:

for(int j=i; j<=i*i; j += i)
    // ... blah ...