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

81. Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

List-I (Recursive Algorithm)List-II (Recurrence Relation)
P.Binary searchI.T(n) = T(n - k) + T(k) + cn
Q.Merge sortII.T(n) = 2T(n - 1) + 1
R.Quick sortIII.T(n) = 2T(n/2) + cn
S.Tower of HanoiIV.T(n) = T(n/2) + 1
Which of the following is the correct match between the algorithms and their recurrence relations?
Codes:
 PQRS
(a)IIIIIIVI
(b)IVIIIIII
(c)IIIIIIVI
(d)IVIIIIII

  • Option : B
  • Explanation :
     Algorithm Recurrence Relation
     P. Binary Search IV. T (n) = T (n/2) + 1
     Q. Merge Sort III. T (n) = 2T (n/2) + cn
     R. Quick Sort I. T (n) = T (n-k) + T (K)
     S. Tower of Hanoi II T (n) = 2T (n-1)+1
Cancel reply
Cancel reply

82. Suppose there are log n sorted lists of n/log n elements each. The time complexity of producing a sorted list of all these elements is:
(Hint: Use a heap data structure)

  • Option : A
  • Explanation :
    x = n/logn
    y = logn
    we get O(n/logn * logn * log logn)
    So O (n log logn)
Cancel reply
Cancel reply

83. Which of the following sorting algorithms has the lowest worst-case complexity?

  • Option : A
  • Explanation :
    Merge sort has lowest worst – case complexity, i.e. O(n log n), whereas all remaining three has O(n2)
Cancel reply
Cancel reply

84. A list of n strings, each of length n, is sorted into lexicographic order using the merge sort algorithm. The worst case running time of this computation is

  • Option : B
  • Explanation :
    Recurrence relation for merge sort
    T (n) = 2 T (n/2) + n
    So T (n) = O(n logn)
    but instead of integers whose comparison take O(1) time, we are given n strings so to compare strings we need O(n) time hence complexity is Q(n2 logn)
Cancel reply
Cancel reply

85. Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

  • Option : C
  • Explanation :
    Given: n numbers
    To find: Tightest upper bound on number of swaps required to sort n numbers using selection sort.
    Analysis: In selection sort, in the unsorted part of the array, we find the minimum element and swap it with the value placed at the index where the unsorted array starts.
    Hence, for each element to put it in its sorted position, we will do some swaps. In each iteration, when we find the minimum and place it in its sorted position, we do only one swap. There are n such iterations, since maximum number of positions to sort is n.
    Hence, there are n.O(1) swaps
    ⇒ O(n) swaps.
    ∴ The solution is (C)
Cancel reply
Cancel reply
Related Quiz.
Performance Analysis of Algorithms and Recurrences