PA of Algorithms Q65

65Consider the following function:

int unknown (int n)

{
int i, j, k = 0;
for (i = n/2; i < = n; i++)
for(j = 2; j< = n; j = j*2)
k = k + n/2;
return (k);
}
The return value of the function is

Option : B
Explanation :
Θ(n³)
So, this is in Θ(log n)
Hence Answer is (B)
The outer for-loop goes for iterations. The inner for-loop runs independent of the otuer loop. And for each inner iteration n/2 gets added to k.
∴ Answer = n/2 x # outer loops x #Inner loops per outer loop
# Inner loops = Θ(log n) [∵2^{Θ(log n)} = Θ(n)]
∴ Answer =

Forgot your password?

I agree with the Terms.