1.2k views

Give the correct matching for the following pairs:

 (A) $O (\log n)$ (P) Selection sort (B) $O (n)$ (Q) Insertion sort (C) $O (n \log n)$ (R) Binary search (D) $O (n^2)$ (S) Merge sort
1. $\text{A-R B-P C-Q D-S}$

2. $\text{A-R B-P C-S D-Q}$

3. $\text{A-P B-R C-S D-Q}$

4. $\text{A-P B-S C-R D-Q}$

edited | 1.2k views

• Selection sort $: O(n^2)$
• Merge sort $:O(n \log n)$
• Binary search $:(\log n)$
• Insertion sort $:O(n)$

Note: if we use $O(n^2)$ for Insertion sort, we will not be having any suitable choice to fill selection sort. So, we can assume that the question is asking for best case time complexities.

edited by
+7
Yes. The given complexities are the best case ones.
0
It is given for selection , O(n) is required for that. Option A will be the answer in my opinion
0
Selection without telling what to select is ambiguous -- it should be selection sort only.
0
It might be to select any element from n element .

So it might be like linear search .

I think option b
0
so, what is the correct answer @Arjun sir?
+2
for Binary Search, best case is O(1)

A) O(logN) -> Binary Search. No other option Matches -> R . Option C & D eliminated.

C) O(nlogn) => Merge sort, even in best worst or any case. -> S  Option A eliminated.

It seems to me that all options are wrong here. But I would go with

Option B) A-R  B-P  C-S  D-Q

D => Q This is okay.

B=> P It is okay if we just have selection. Selection sort is O(N2)

–1 vote

Option B ...

1
2