Follow Us :

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

66. Which one of the following correctly determines the solution of the recurrence relation with T(1)= 1?

  • Option : A
  • Explanation :
    Since f(n) = log n
    a = 2, b = 2
    finding logba using master’s method = log22 = 1
    Hence, f(n) = n'
    So, T(n) = Θ(n)
Cancel reply
Cancel reply

67. Suppose we have a balanced binary search tree T holding n-numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T.
If the tightest upper bound on the time to compute the sum is O(na logbn + mc logdn), the value of α + 10b + 100c + 1000d is ____.

  • Option : A
  • Explanation :
    The time complexity is O (m + logn)
    So C = 1, d = 0, a = 0, b = 1
    0 + 10 × 1 + 100 × 1 + 1000 × 0 = [110]
Cancel reply
Cancel reply

68. Consider the following C function.

 { 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
Cancel reply
Cancel reply

69. An algorithm performs (logN)1/2 find operations, N insert operations, (logN)1/2 delete operations, and (logN)1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

  • Option : A
  • Explanation :
    Unsorted array
    The algorithm perform
    find operation (log N)½
    Insert operation N
    delete operation (log N)½
    decrease key operations (log N)½
    Hence unsorted array is best data structure for all above operations.
Cancel reply
Cancel reply

70. Consider a complete binary tree where the left and the right subtrees of the root are maxheaps. The lower bound for the number of operations to convert the tree to a heap is

  • Option : A
  • Explanation :
    The subtrees are already Max-heap, so to make it half, we have to heap if the root, which takes Ω(log n) time.
Cancel reply
Cancel reply
Related Quiz.
Performance Analysis of Algorithms and Recurrences