Question

Match List - I with List - II. 

List - I		List - II
A.	Binary search	I.	Queue
B.	Merge sort	II.	Stack
C.	Depth First Search (DFS)	III.	\(T(n) = 2T(n/2) + n\)
D.	Breadth First Search (BFS)	IV.	\(T(n) = T(n/2) + 1\)

Choose the correct answer from the options given below:

• A. A-III, B-IV, C-I, D-II
• B. A-I, B-II, C-III, D-IV
• C. A-IV, B-III, C-II, D-I
• D. A-II, B-IV, C-III, D-I

Hint:

Recurrence Tip: If it works on both halves, it's $2T(n/2)$ (Merge Sort). If it works on one half, it's $T(n/2)$ (Binary Search).

Answer 1

The Correct Option is C

We match algorithms with their characteristic recurrence relations or the data structures they utilize. 1. Binary Search (A-IV): Binary search divides the search space in half at each step and processes only one half. Its recurrence is $T(n) = T(n/2) + 1$, leading to $O(\log n)$. 2. Merge Sort (B-III): Merge sort divides the array into two halves, recursively sorts both, and then merges them. Its recurrence is $T(n) = 2T(n/2) + n$, leading to $O(n \log n)$. 3. Depth First Search (C-II): DFS explores as far as possible along each branch before backtracking. It uses a Stack (either explicitly or via the recursion stack). 4. Breadth First Search (D-I): BFS explores all neighbors at the current depth before moving to the next level. It uses a Queue to keep track of discovered but unvisited nodes.