Test by Bikram | Mock GATE | Test 3 | Question: 14

Question

We write a new algorithm by considering the fact that number of comparisons required by Selection Sort can be reduced by considering elements in pairs and finding the minimum and maximum element at the same time.

What will be the time complexity of the new algorithm for comparisons of Selection Sort?

• A.    $O/2$
• B.    $O(n)/4$
• C.    $O(n)$
• D.    $O$$(\log n)$

Comments

options are not clear.

---

Selection sort usually takes $\frac{n^2}{2}$ comparisons.

I believe by taking pairs, we'll reduce the comparisons by a factor of 2 (ie $\frac{n^2}{4}$)

This is still $O(n^2)$

 

What did I miss? :(

Answer 1

The new algorithm will only reduce the number of comparisons but will not reduce the complexity.

Comments

@ Bikram sir

no of comparisions will be O(n²).

So why we are getting time complexity of O(n)?

Also according to the provided link above https://www.macs.hw.ac.uk/~pjbk/pathways/cpp2/node67.html

---

@kash0611

The screenshot you posted doesn't mention about the modification being done here in the question. This is the unmodified version right..?

Also the link is broken..

@Bikram Sir, please elaborate a bit..

---

@Bikram Sir, Can you please elaborate how the element pair will reduce the comparison complexity (by taking any example) because I think that even if we take pair we will still need each element to compare with the current_max and current_min element , which would make the comparisons same.

my thinking may not be correct, so please correct me !

@GO_user