retagged by
7,741 views
26 votes
26 votes

Give the correct matching for the following pairs: $$\begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(P)} & \text{Selection} \\\hline  \text{(B)} & \text{$O (n)$} & \text{(Q)}& \text{Insertion sort} \\\hline   \text{(C)}& \text{$O (n \log n)$} & \text{(R)}  & \text{Binary search} \\\hline  \text{(D)} & \text{$O (n^2)$} &\text{(S)}  & \text{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}$

retagged by

3 Answers

Best answer
29 votes
29 votes

Here we are talking about the worst case time complexities of the given algorithms. Selection actually refers to selection algorithm and not selection sort.

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

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

Correct Answer: $B$

selected by
15 votes
15 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)

3 votes
3 votes

here

        A) (Ologn)-> Binary search

        B) O(n)   -> max no of swap in selection sort in worst case.

       C)  O(nlogn) -> marge sort 

       D)  O(n^2)  -> No of swap (moment)  in insertion sort in worst case

hance B is correct answer...........

Answer:

Related questions

25 votes
25 votes
2 answers
2
Kathleen asked Sep 25, 2014
9,053 views
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?Dynamic programmingBacktrackingGreedyDivide and Conqu...
31 votes
31 votes
8 answers
3
Kathleen asked Sep 25, 2014
10,203 views
Which normal form is considered adequate for normal relational database design?$2NF$$5NF$$4NF$$3NF$
19 votes
19 votes
4 answers
4
Kathleen asked Sep 25, 2014
13,870 views
A counting semaphore was initialized to $10$. Then $6 P$ (wait) operations and $4V$ (signal) operations were completed on this semaphore. The resulting value of the semap...