0 votes 0 votes 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? $O/2$ $O(n)/4$ $O(n)$ $O$$(\log n)$ GATE tbb-mockgate-3 algorithms sorting algorithm-design + – Bikram asked Feb 9, 2017 retagged Sep 15, 2020 by ajaysoni1924 Bikram 587 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Rishabh Gupta 2 commented Feb 1, 2018 reply Follow Share options are not clear. 1 votes 1 votes JashanArora commented Jan 16, 2020 reply Follow Share 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? :( 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes The new algorithm will only reduce the number of comparisons but will not reduce the complexity. Bikram answered Feb 9, 2017 selected Sep 9, 2019 by Bikram Bikram comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments kash0611 commented Jan 6, 2018 reply Follow Share @ 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 1 votes 1 votes GO_user commented Jan 6, 2019 reply Follow Share @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.. 0 votes 0 votes jiminpark commented Dec 28, 2021 reply Follow Share @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 0 votes 0 votes Please log in or register to add a comment.