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

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

asked in Algorithms by Veteran (59.9k points)
edited by | 1.3k 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. 

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)
+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 (43.5k points)
0 votes

Option B ... 

Some additional information ....

answered by Boss (12.3k 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
47,881 questions
52,231 answers
67,649 users