Match List - I with List - II. f(n) = af(n/b) + g(n) is a divide-and-conquer recurrence relation the Listed-I algorithms, match their recurrence in Listed-II.
|
LIST - I Divide-and-conquer based algorithms |
LIST - II Recurrence Relation |
||
|
A. |
Binary Search |
I. |
f(n) = 7f(n/2) + 15 n2/4 |
|
B. |
Find maximum and minimum of a sequence |
II. |
f(n) = 2f(n/2) + n |
|
C. |
Merge Sort |
III. |
f(n) = 2f(n/2) + 2 |
|
D. |
Fast Matrix Multiplication |
IV. |
f(n) = f(n/2) + 2 |
Choose the correct answer from the options given below:
1
A - I, B - II, C - III, D - IV
2
A - II, B - III, C - IV, D - I
3
A - III, B - IV, C - I, D - II
4
A - IV, B - III, C - II, D - I