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

so should the complexity not be O(n^2) where as the number of comparison are O(n)?

---

No , complexity will be same .

---

Sir,

will the factors /2 and /4 in options A and B be absorbed by the O notation and eventually become  O(n) right ?

---

yes, right, they will eventually become  O(n)

---

@bikram sir
Is it asking for the time complexity of comparisons or the selection sort as a whole, its not clear in the question. Beacause if it's asking time complexity of selection sort, shouldn't it be O(n^2)?

---

yes, it is asking for the time complexity of comparisons of selection sort only. And not the selection sort as a whole ( which have O(n²) time complexity ) 

For selection sort, number of comparison is O(n) , read https://www.macs.hw.ac.uk/~pjbk/pathways/cpp2/node67.html

---

@ 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