How to determine time complexity of below code

Question

public void test(int n)
{
   for(i=1;i<=n;i=i*2)
  {
     for(j=1;j<n;j=j+(j*i))
      {
         // some code
      }
  }
}

Above code has two loop. The outer loop which execute log(n) times. How can we calculate the number of times inner loop will execute? What will be time complexity of above code?

Answer 1

The inner loop takes log_{i+1}(n) time (log base i+1 of n). Assuming n is a power of 2, and using the change of base formula, to convert to base 2: log_{i+1)(n) = lg(n)/lg(i+1), that means the "some code" will be executed this many times: lg(n)/lg(2) + lg(n)/lg(3) + lg(n)/lg(5) + ... + lg(n)/lg(n+1).

Now, 1/lg(2) + 1/lg(3) + ... + 1/lg(n+1) <= 1 + 1/lg(2) + 1/lg(4) + ...1/lg(n) = 1 + 1/1 + 1/2 + 1/3 + ... + 1/lg(n) ~= (1 + log(lg(n))).

Similarly, 1/lg(2) + 1/lg(3) + ... + 1/lg(n+1) >= 1/lg(4) + 1/lg(8) + ... + 1/lg(2n) ~= (log(lg(2n)) - 1). (Using an approximation to the harmonic numbers: H(n) ~= log(n)).

Thus it seems that the complexity is log(n)log(log(n)).

This is a pretty sketchy proof, but hopefully will point you in the right direction.