Match List-I with List-II. $$\begin{array}{|c|l|c|}\hline\textbf{List-I (Algorithm)} & & \textbf{List-II (Recurrence relation)} \\ \hline (A)\ \text{Binary Search} & \quad & (I)\ T(n)=T(n/2)+c \\ \hline (B)\ \text{Merge Sort} & \quad & (II)\ T(n)=2T(n/2)+\Theta(n) \\ \hline (C)\ \text{Quick Sort (worst case)} & \quad & (III)\ T(n)=T(n-1)+\Theta(n) \\ \hline (D)\ \text{Linear Search} & \quad & (IV)\ T(n)=T(n-1)+c \\ \hline \end{array}$$ (where c is a constant)
Step-by-step Solution:
Step 1: Analyze each algorithm recurrence
(A) Binary Search: At each step the array size reduces by half, so recurrence is: \[ T(n) = T(n/2) + c \]
(B) Merge Sort: Array is divided into two halves and merged in linear time, so recurrence is: \[ T(n) = 2T(n/2) + \Theta(n) \]
(C) Quick Sort (Worst Case): In the worst case, one partition has size \(n-1\), so recurrence is: \[ T(n) = T(n-1) + \Theta(n) \]
(D) Linear Search: Each comparison reduces size by 1, so recurrence is: \[ T(n) = T(n-1) + c \]
Step 2: Final Matching
| List-I (Algorithm) | List-II (Recurrence Relation) |
|---|---|
| (A) Binary Search | (I) \(T(n) = T(n/2) + c\) |
| (B) Merge Sort | (II) \(T(n) = 2T(n/2) + \Theta(n)\) |
| (C) Quick Sort (Worst Case) | (III) \(T(n) = T(n-1) + \Theta(n)\) |
| (D) Linear Search | (IV) \(T(n) = T(n-1) + c\) |
✅ Correct Answer: (A) → (I), (B) → (II), (C) → (III), (D) → (IV)
Hence, the correct option is Option A.