Question 1788 – Nielit Scientist-B 17-12-2017
November 5, 2023Question 1790 – Nielit Scientist-B 17-12-2017
November 5, 2023Question 11185 – Algorithms
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.
RECURSIVE ALGORITHM RECURRENCE RELATION P. Binary search I. T(n) = T(n-k) + T(k) + cn Q. Merge sort II. T(n) = 2T(n-1) + 1 R. Quick sort III. T(n) = 2T(n/2) + cn S. Tower of Hanoi IV. T(n) = T(n/2) + 1
Correct Answer: B
Question 5 Explanation:
Quick sort – T(n) = T(n-k) + T(k) + cn
Binary search – T(n/2) + 1
Merge sort – T(n) = 2T(n/2)+ cn
Tower of hanoi – T(n) = 2T(n-1) +1
Binary search – T(n/2) + 1
Merge sort – T(n) = 2T(n/2)+ cn
Tower of hanoi – T(n) = 2T(n-1) +1
P-II, Q-III, R-IV, S-I
P-IV, Q-III, R-I, S-II
P-III, Q-II, R-IV, S-I
P-IV, Q-II, R-I, S-III