Consider a list of recursive algorithms and a list of recurrence relations as…
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 106 students.
Show answer & explanation
Correct answer: B
Correct matching and reasoning:
Binary search → T(n) = T(n/2) + 1. Binary search halves the problem size each step, so it has logarithmic time complexity Θ(log n).
Merge sort → T(n) = 2T(n/2) + cn. Merge sort splits into two halves and performs linear-time merging, giving Θ(n log n).
Quick sort → T(n) = T(k) + T(n-k) + cn. Quick sort partitions into two subproblems of sizes k and n−k and does linear partitioning; the average-case is Θ(n log n), though the exact recurrence depends on the pivot choices.
Tower of Hanoi → T(n) = 2T(n-1) + 1. Solving for n disks requires solving for n−1 twice plus one move, giving exponential time Θ(2^n).
Therefore the correct mapping is: Binary search ↔ T(n)=T(n/2)+1; Merge sort ↔ T(n)=2T(n/2)+cn; Quick sort ↔ T(n)=T(k)+T(n-k)+cn; Tower of Hanoi ↔ T(n)=2T(n-1)+1.