Question

Match the following algorithms with their worst-case time complexities.

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

Hint:

Remember the standard worst-case complexities: \[ \text{Linear Search} = O(n) \] \[ \text{Binary Search} = O(\log n) \] \[ \text{Selection Sort} = O(n^2) \] These are among the most frequently asked complexities in competitive exams and interviews.

Answer 1

The Correct Option is B

Concept: The worst-case time complexity of an algorithm represents the maximum number of operations performed for the most unfavorable input of size \(n\). To solve matching questions, we must know the standard complexities of the given algorithms.

Step 1: Determine the complexity of Linear Search.
In Linear Search, elements are examined one by one until the desired element is found. In the worst case, the element is either absent or present at the last position. Hence all \(n\) elements are checked. \[ T(n)=O(n) \] Therefore, \[ A \rightarrow II \]

Step 2: Determine the complexity of Binary Search.
Binary Search repeatedly divides the search interval into two equal halves. After each comparison, the search space becomes half. Thus, \[ n,\;\frac{n}{2},\;\frac{n}{4},\;\frac{n}{8},\ldots \] The number of divisions required is \[ \log_2 n. \] Therefore, \[ T(n)=O(\log n) \] Hence, \[ B \rightarrow III \]

Step 3: Determine the complexity of Selection Sort.
Selection Sort repeatedly finds the minimum element from the unsorted portion. The total comparisons performed are \[ (n-1)+(n-2)+\cdots+2+1. \] Using the formula: \[ \frac{n(n-1)}{2}, \] we obtain \[ T(n)=O(n^2). \] Thus, \[ C \rightarrow I \]

Step 4: Write the complete matching.
Combining all results: \[ A \rightarrow II \] \[ B \rightarrow III \] \[ C \rightarrow I \] Therefore, \[ \boxed{\text{A-II,\; B-III,\; C-I}} \]

Step 5: Select the correct option.
Hence the correct answer is \[ \boxed{\text{Option (B)}} \]