Consider a list of recursive algorithms and a list of recurrence relations as…
PYQ GATE 2004
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 HanoiI | V.T(n) = T(n/2) + 1 |
- A.
P-II, Q-III, R-IV, S-I
- B.
P-IV, Q-III, R-I, S-II
- C.
P-III, Q-II, R-IV, S-I
- D.
P-IV, Q-II, R-I, S-III
Attempted by 293 students.
Sign up free to check your answer
Sign up freeLoading lesson…