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: Algorithmic Complexity Analysis.
- Binary Search (A): For a sorted array, binary search has a time complexity of $O(\log n)$. This is represented by the recurrence relation $T(n) = T(n/2) + c$ (I).
- Merge Sort (B): Merge Sort recursively divides the array into two halves and combines the results linearly. Its recurrence relation is $T(n) = 2T(n/2) + \Theta(n)$ (II).
- Quick Sort (worst-case partitioning) (C): In its worst-case scenario, quick sort's performance is comparable to selection sort, with the recurrence $T(n) = T(n-1) + \Theta(n)$ (III).
- Linear Search (D): Linear search examines each element sequentially, resulting in the recurrence $T(n) = T(n-1) + c$ (IV).

Step 2: Final Alignment.
The correct matches are (A) - (I), (B) - (II), (C) - (III), (D) - (IV).