Match List - I with List - II. f(n) = a f(n / b) + g(n) is a divide-and- conquer recurrence relation for the Listed-I algorithms, match their recurrence in Listed-II.

1. AA-I, B-II, C-III, D-IV
2. BA-II, B-III, C-IV, D-I
3. CA-III, B-IV, C-I, D-II
4. DA-IV, B-III, C-II, D-I

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: D. A-IV, B-III, C-II, D-I

Explanation

Binary search: f(n) = f(n/2) + 2. Max-min: f(n) = 2f(n/2) + 2. Merge sort: f(n) = 2f(n/2) + n. Fast (Strassen) matrix multiplication: f(n) = 7f(n/2) + 15n²/4.