PA of Algorithms Q81
| List-I (Recursive Algorithm) | List-II (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 |
Which of the following is the correct match between the algorithms and their recurrence relations?
Codes:
| P | Q | R | S | |
| (a) | II | III | IV | I |
| (b) | IV | III | I | II |
| (c) | III | II | IV | I |
| (d) | IV | II | I | III |
- 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
