Question

Match List-I with List-II:
\[\begin{array}{|c|c|}\hline \textbf{List-I} & \textbf{List-II} \\ \hline (A)\ \text{Binary Search} & (I)\ T(n) = T(n/2) + c \\ \hline (B)\ \text{Merge Sort} & (II)\ T(n) = 2T(n/2) + \Theta(n) \\ \hline (C)\ \text{Quick Sort (worst case)} & (III)\ T(n) = T(n-1) + \Theta(n) \\ \hline (D)\ \text{Linear Search} & (IV)\ T(n) = T(n-1) + c \\ \hline \end{array}\] Choose the correct answer from the options given below:

• (A) - (I), (B) - (II), (C) - (III), (D) - (IV)
• (A) - (III), (B) - (I), (C) - (IV), (D) - (II)
• (A) - (I), (B) - (III), (C) - (IV), (D) - (II)
• (A) - (III), (B) - (IV), (C) - (II), (D) - (I)

Hint:

The time complexity of algorithms like Merge Sort and Quick Sort can be understood using their respective recurrence relations. Binary Search and Linear Search also have characteristic recursions.

Answer 1

The Correct Option is A

Step 1: Analysis of Algorithms.
- **Binary Search** (A): The time complexity for binary search in a sorted array is **$O(\log n)$**, which corresponds to the recurrence relation **$T(n) = T(n/2) + c$** (I).
- **Merge Sort** (B): Merge Sort divides the array into two halves recursively, with a linear combination of the subproblems, leading to the recurrence **$T(n) = 2T(n/2) + \Theta(n)$** (II).
- **Quick Sort (worst case partitioning)** (C): In the worst case, quick sort behaves like selection sort with recurrence **$T(n) = T(n-1) + \Theta(n)$** (III).
- **Linear Search** (D): Linear search performs a sequential scan of the list, giving the recurrence **$T(n) = T(n-1) + c$** (IV).

Step 2: Conclusion.
The correct matching is **(A) - (I), (B) - (II), (C) - (III), (D) - (IV)**.