0

Looking for help on how to find time complexity here:

void f(int n)
{
 for(int i=0; i<n; ++i)
     for(int j=0; j<i; ++j)
         for(int k=i*j; k>0; k/=2)
             printf("~");
}

What I tried so far is noticing the inner loop runs log(i*j) times for O(1) for each received combination of i,j. So I got:

log(n(n-1))+log(n(n-2))+...+log(n)+log((n-1)(n-2))+...+log(n-1)+...+...+log(1) but I can't find how to simplify it.
Red
  • 26,798
  • 7
  • 36
  • 58
paxtibimarce
  • 101

1 Answers1

0

I'm not a specialist on this field, but maybe my consideration helps.

The two outer loops cause n*(n - 1)/2 executions of the innermost loop. That makes a complexity of O(n^2)

The innermost loop has a logarithmic complexity. And since log(n^2) = 2log(n), it'll be something like O(log(n)), yielding a total complexity of O(n^2 log(n)).

If you look at your sum of logarithms, you'll find that most arguments are greater than n. In fact, there are (n - 1)^2 arguments that exceed n and only n - 1arguments less than n.

And if you're not convinced by my reasoning above, maybe it helps if you consider that log(a) + log(b) = log(ab). IOW your sum equals log(n(n - 1)!)

Ronald
  • 2,842
  • 16
  • 16