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?
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(n2) 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(n2).
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
64.3k questions
77.9k answers
244k comments
80.0k users