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!

Jean-François Fabre · Accepted Answer · 2019-03-11 17:16:25Z

3

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.

edited Mar 11, 2019 at 17:16

answered Mar 11, 2019 at 17:09

Jean-François Fabre♦

141k24 gold badges179 silver badges246 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Antti Haapala Over a year ago

Exactly. More precisely, first loop is n, second clearly n/2 average, and inner is some factor times log n²; and log n² is 2 log n. Then remove the constant factor.

alinsoar · Accepted Answer · 2019-03-12 08:31:21Z

1

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

edited Mar 12, 2019 at 8:31

answered Mar 11, 2019 at 18:46

alinsoar

15.9k4 gold badges63 silver badges80 bronze badges

Collectives™ on Stack Overflow

Calculating the complexity of this function

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related