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

Concept:
• Divide and Conquer algorithms are often described by recurrence relations that show how the problem is split and combined.
• Graph traversal algorithms are distinguished by the data structures used to track the "frontier" of exploration.

Step 1: Match A (Binary search)
Binary search works by splitting a sorted array in half and discarding one half in each step. The time complexity is defined by the recurrence \(T(n) = T(n/2) + 1\), leading to \(O(\log n)\). This matches with IV.

Step 2: Match B (Merge sort)
Merge sort splits the array into two halves, recursively sorts them, and then merges them in linear time. Its recurrence is \(T(n) = 2T(n/2) + n\), leading to \(O(n \log n)\). This matches with III.

Step 3: Match C (Depth first search)
DFS explores as far as possible along each branch before backtracking. This "Last-In, First-Out" behavior is implemented using a Stack (either explicitly or via the recursion stack). This matches with II.

Step 4: Match D (Breadth first search)
BFS explores all neighbors at the present depth level before moving on to nodes at the next depth level. This "First-In, First-Out" behavior is implemented using a Queue. This matches with I.