UGC NET CSE | January 2025 | Part 2 | Question: 63

Question

Match the LIST-I with LIST-II

$\begin{array}{|l|l|l|l|} \hline & \textbf{LIST-I}  & & \textbf{LIST-II} \\ 
& \textbf{Algorithm} & & \textbf{Complexity} \\ \hline  \text{A.} & \text{Insertion Sort} & \text{I.} & \mathrm{O}(\log \mathrm{n}) \\ \hline \text{B.} & \text{Binary Search} & \text{II.} &  \mathrm{O}\left(\mathrm{n}^{2}\right) \\ \hline \text{C.} & \text{Quick Sort} & \text{III.} & \mathrm{O}(\mathrm{n}-1)  \\ \hline \text{D.} & \text{Selection Sort} & \text{IV.} & \mathrm{O}(\mathrm{n} \log \mathrm{n}) \\ \hline \end{array}$

Choose the correct answer from the options given below:

• A. $\text{A-III, B-I, C-IV, D-II}$
• B. $\text{A-II, B-III, C-I, D-IV}$
• C. $\text{A-I, B-II, C-IV, D-III}$
• D. $\text{A-II, B-III, C-IV, D-I}$

Answer 1

The correct answer is (C) A-II, B-I, C-IV, D-III.

Insertion Sort has a time complexity of O(n²) because in the worst case (when the array is in reverse order), every element must be compared and shifted for each insertion. Binary Search runs in O(log n) since it repeatedly divides the search interval in half. Quick Sort, on average, performs in O(n log n) as it partitions the array around a pivot and recursively sorts the subarrays. Selection Sort takes O(n – 1) passes, because it finds the minimum element and places it in the correct position during each iteration. Therefore, the correct matching is A-II, B-I, C-IV, D-III.

Comments

It Illogical that selection sort has worst case time complexity of O(n-1) = O(n), viz Linear Time. 

Selection sort selects an index (from  n indices) , find the smallest element of (n-1) elements to right, and swaps them 

=> TC(selection sort) = O(n^2).

Even best case is Ω(n^2).

The question is not setup correctly.