CODEWITHSUNDEEP
cloopsfor-loopcomplexity-theory
Kodak3993
Kodak3993

Reputation: 21

How to calculate the complexity of this function?

I'm wondering what is the time-complexity of the inner for-loop, is it sqrt(n) or log(n)?

void foo(int n)
{
 for (int i=0; i<n*n; ++i)
     for (int j=1; j*j<n; j*=2)
         printf("Hello there!\n");
}

Upvotes: 0

Views: 64

Answers (2)

Fanchen Bao
Fanchen Bao

Reputation: 4289

I think the inner for-loop has complexity O(sqrt(n)). To make it O(log(n)), the inner for loop should be something like this:

EDIT

It should be O(log(n)).

Upvotes: 0

user991306
user991306

Reputation: 35

j in inner for loop will take values 1,2,4,...2^t

Also according to constraint given, 2^2t = n

So, t = (1/2)logn

Therefore the inner loop should have Time Complexity O(log(n))

Upvotes: 3

Related Questions