Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences

Avatto>>UGC NET COMPUTER SCIENCE>>PRACTICE QUESTIONS>>Data Structures and Algorithms>>Performance Analysis of Algorithms and Recurrences

48. Consider the following C-program fragment in which i, j, and n are integer variables.
for(i = n, j = 0; i > 0; i/ = 2, j + = i);
Let val (j) = denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

  • Option : C
  • Explanation :
    If n is a power of 2, then
    term
    If n is not a power of 2, then there will be minor differences of 1 at wherever is odd.
    Hence val(j) computed on the basis of n = 2n will give a fair answer

    = 2(n – 1) = θ(n)
Cancel reply
Cancel reply

49. Consider the following recurrence
T(n) = 2T([√n]) + 1,T(1) = 1
Which one of the following is true?

  • Option : B
  • Explanation :
    T(n) = 2T(√n) + 1
    Put n = 2k
    T(2k) = 2T(nk/2) + 1
    replace T(2k) by S(k)
    S(k) = 2 S(k/2) + 1
    Apply masters
    Klog22 ⇒ k > 1
    So Θ(k)
    Now we know n = 2k, k = log2(n)
    then Θ(logn)
Cancel reply
Cancel reply

50. Consider the following segment of C code
int j, n;
j = i;
while (j < = n)
j = j*2;
The number of comparisons made in the execution of the loop for any n > 0 is

  • Option : D
  • Explanation :
    Since, j increases in power of 2's.
    if statement j = j * 2 executes k times, then
    2k < n
    ⇒ k < log2 n
    Since k will be integer,
    total number of comparison
    (when loop exits)
Cancel reply
Cancel reply