Complexity calculation [closed]

Question

What is the complexity of:

int f4(int n)
{
   int i, j, k=1, count = 0;

   for(i = 0; i < n; i++) 
   {
      k *= 3;

      for(j = k; j; j /= 2)
         count++;
   }

   return count;
}

I know it is O(n^2) but how do you calculate this? and why isn't it n*log n?

Answer 1

There are n outer loops. At any point, k = 3i. There are log2(k) inner loops (because we halve j on each iteration.)

log2(3i) = log3 (3i) / log3(2) = i / (constant)

So the complexity of the inner loop is i. In other words, this program has the same complexity (but not the exact same number of iterations) as

int f4changed(int n)
{
   int i, j, count = 0;

   for(i = 0; i < n; i++) 
   {
      for(j = 0; j < i; j++)
      {
          count++;
      }
   }
}

This is O(n2) as you've already seen.