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?

Having looked at your other questions, it seems you're just trying to get your current homework assignment done... Good luck with that :-) — Shalom Craimer, Feb 15 '09 at 09:46
I'm looking for answers to some HW questions which I'm not sure how to solve by myself but I'm not trying to get it all done by others. I'm just trying to understand how complexity works. — yyy, Feb 15 '09 at 10:47
Corman Leisterson Rivest and Stein. The Big White Book. Ask for it by name. — Brian Postow, Dec 03 '09 at 22:04

score 21 · Accepted Answer · edited May 23 '17 at 12:26

21

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

log2(3ⁱ) = log3 (3ⁱ) / 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(n²) as you've already seen.

edited May 23 '17 at 12:26

Community

1
1

answered Feb 15 '09 at 09:23

Jon Skeet

1,421,763
867
9,128
9,194

May I suggest writing `3ⁱ` for the power, to avoid any possible confusion with bitwise xor? – Hosam Aly Mar 03 '09 at 12:50

score 2 · Answer 2 · edited May 23 '17 at 10:32

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).

score 0 · Answer 3 · answered Feb 15 '09 at 09:38

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)) = 2*Log(Pow(2,n)).

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

Complexity calculation

3 Answers3