Calculating the complexity of this function

Question

This is the function:

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("~");
}

In my opinion, the calculation of the time complexity would end up to be something like this:

log((n-1)(n-2))+log((n-1)(n-3))+...+log(n-1)+log((n-2)(n-3))+...+log(n-2)+...log(2)

So, I get a time complexity of nlog(n!) (because loga+logb=log(a*b) and because n-1,n-2,n-3,... each appears n-1 times in total.

However, the correct answer is n^2*logn, and I have no idea where my mistake is. Could anyone here help?

Thanks a lot!

Answer 1

log(n!) can be approximated as (n+1/2)log(n) - n + constant (see https://math.stackexchange.com/questions/138194/approximating-log-of-factorial)

So the complexity is n*n*log(n) as expected.

Simpler: compute the complexity loop by loop independently and multiply them.

First 2 outer loops: trivial: n each, which makes n^2

Inner loop: has a log(n**2) complexity which is the same as log(n)

So n^2log(n) is the correct answer.

Answer 2

The Complexity is O(N*N*LOG_2(N^2)).

The first and the second loop both have O(N) and the last loop in k has logarithmic grow.

LOG_2(N^2) = 2*LOG_2(N) and
O(N*M)=O(N)*O(M).
O(constant)=1.

So for the grow of the last loop you can write also O(LOG_2(N^2))=O(LOG(N)).