PA of Algorithms Q68

68Consider the following C function.

int fun 1 (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=l; k<p; k=k*2)
++q;
} return q;
}
Which one of the following most closely approximates the return value of the function fun1?

Option : D
Explanation :
* Outer loop (for i) executed n times.
* Loop (for j) executed logn times so value of p = logn.
loop (for k) executed log p times.
So value of q = log p = log logn.
for every value of i loop (k) is executed so return value is n * log logn

Forgot your password?

I agree with the Terms.