Teaching HPSC Lecturer (Technical) Mock Test 2024 Algorithms Asymptotic Worst Case Time and Time Complexity Introduction
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 |
Which of the following is the correct match between the algorithms and their recurrence relations?
1
P – II Q – III R – IV S – I
2
P – IV Q – III R – I S – II
3
P – III Q – II R – IV S – I
4
P – IV Q – II R – I S – III
5
Question Not Attempted