The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes

Give the correct matching for the following pairs: 
$$\begin{array}{l|l}\hline \text{(A) $O (\log n)$}  &  \text{(P) Selection sort} \\\hline  \text{(B) $O (n)$} & \text{(Q) Insertion sort} \\\hline  \text{(C) $O (n \log n)$} & \text{(R) Binary search} \\\hline  \text{(D) $O (n^2)$} & \text{(S) Merge sort} \\\hline \end{array}$$

  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}$

asked in Algorithms by Veteran (52k points)
edited by | 1.5k views

3 Answers

+16 votes
Best answer
  • 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. 

Correct Answer: $B$

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

So it might be like linear search .

I think option b
so, what is the correct answer @Arjun sir?
for Binary Search, best case is O(1)
selection sort==O(n^2) (best case, Worst case, avg case)

insertion sort==O(n)(best case)

binary search ==O(logn) (worst case ,avg case)

merge sort ==O(nlogn) (best case, worst case, avg case)
+13 votes

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)

answered by Boss (41k points)
0 votes

Option B ... 

Some additional information ....

answered by Boss (11.6k points)
disabled videos

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,122 answers
71,039 users