Time complexity

Question

Q2.  Consider the  following  C  function:

int  fun1 (int  n)

{ int  i, j, k, p, q =  0;

for  (i = 1; i<n; ++i)

{ p =  0;

for  (j=n; j>1; j=j/2) ++p;

for  (k=1; k<p; k=k*2) ++q; }

return q; } Which one  of the  following  most  closely  approximates the  return value of  the function fun1?

(a) n3        (c) nlogn      (b)  n (logn)^2 (d)  nlog(logn)

Comments

i think it should be n log (log n)^2

---

answer is given nlog(log n)
please explain your logic how u solved it

Answer 1

Return value of q = O(n log log n) and Time Complexity = O( n log n).

Explanation: Outer for loop will run for 'n' times.

For every value of i, the inner loop for  (j=n; j>1; j=j/2) ++p; will run for (log n) times.

Now the value of 'p' will be approximately log n.

So the other for loop for  (k=1; k<p; k=k*2) ++q; will run for (log log n) times.

Note: for  (k=1; k<p; k=k*2) ++q; is not nested loop of for  (j=n; j>1; j=j/2) ++p;.

As the outer loop is running for almost n times.

Time Complexity = O( n log n   +   n log log n) = O(n log n).

But the return value of q will be (n log log n).