Complexity calculation

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.

Answer 2

i = 1 results in 3 iterations (of the inner loop) (3, 1, 0)
i = 2 is 8 (5 then 3)
i = 3 is 13 (7 + 5 + 3)

What you have is approximating an arithmetic series, which is O(n²).

For completeness (and to explain why the exact number of iterations doesn't matter), refer to the Plain english explanation of Big O (this is more for other readers than you, the poster since you seem to know what's up).

Answer 3

The complexity of Log(Pow(3,n)) ~ O(N). If the inner loop was k = 2, then the number of iterations would have also been n.
For calculating O(~) the highest power term is used and the others are neglected. Log(Pow(3,n)) can be bounded as:
Log(Pow(2,n)) <= Log(Pow(3,n)) <= Log(Pow(4,n))
Now Log(Pow(4,n)) = 2Log(Pow(2,n)).

The highest power term here is n (as 2 is a constant).