Solution

The correct answer is A - IV, B - III, C - II, D - I

Key Points

• A. Binary Search
  • Binary Search is a divide-and-conquer algorithm that works by repeatedly dividing the search interval in half.
  • The recurrence relation for Binary Search is: f(n) = f(n/2) + 2
  • Correct match: IV. f(n) = f(n/2) + 2
• B. Find maximum and minimum of a sequence
  • This problem involves dividing the sequence into two halves, finding the maximum and minimum in each half, and then combining the results.
  • The recurrence relation is: f(n) = 2f(n/2) + 2
  • Correct match: III. f(n) = 2f(n/2) + 2 $f(n)=2f(n/2)+2$
• C. Merge Sort
  • Merge Sort is a divide-and-conquer algorithm that divides the array into two halves, sorts them, and then merges the sorted halves.
  • The recurrence relation for Merge Sort is: f(n) = 2f(n/2) + n
  • Correct match: II. f(n) = 2f(n/2) + n
• D. Fast Matrix Multiplication
  • Fast Matrix Multiplication algorithms, such as Strassen's algorithm, divide the matrices into smaller sub-matrices and then combine the results.
  • The recurrence relation for Fast Matrix Multiplication is: f(n) = 7f(n/2) + 15 n2/4
  • Correct match: I. f(n) = 7f(n/2) + 15 n2/4

Therefore, the correct answer is: A - IV, B - III, C - II, D - I