The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.1k 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}$

asked in Algorithms by Veteran (59.6k points)
edited by | 1.1k views

3 Answers

+14 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.3k points)
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?
0
for Binary Search, best case is O(1)
+12 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 (42.9k points)
–1 vote

Option B ... 

Some additional information ....

answered by Boss (11.4k points)


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

40,903 questions
47,558 answers
146,289 comments
62,306 users