Follow Us :

PA of Algorithms Q65

0. Consider the following function:

 {
  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 :
    Θ(n3)
    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 =
Cancel reply
Cancel reply