GATE CSE 1998 | Question: 1.22

Question

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

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

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

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

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

Comments

Sources : Wikipedia

Answer 1

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$

Comments

According to option B selection sort = O(n). How is it possible ?

---

@srestha @Gaurav nitkkriit  @Soumyabrata Chatterj  @Arjun

Here selection is given not selection sort, So selecting an element in worst case might take O(n) if the element is not sorted.

Hence 

Selection an element (not Selection sort) = O(n)

Merge Sort = O(n log n)

Binary Search = O(log n)

Insertion Sort = O(n^2)

---

@GateOverflow04 Yes, that's correct.

Answer 2

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(N²)

Answer 3

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...........