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 654 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 Aakash Das commented Feb 10, 2017 reply Follow Share so should the complexity not be O(n^2) where as the number of comparison are O(n)? 1 votes 1 votes Bikram commented Feb 10, 2017 reply Follow Share No , complexity will be same . 0 votes 0 votes Harsh181996 commented Mar 13, 2017 reply Follow Share Sir, will the factors /2 and /4 in options A and B be absorbed by the O notation and eventually become O(n) right ? 0 votes 0 votes Bikram commented Mar 13, 2017 reply Follow Share yes, right, they will eventually become O(n) 1 votes 1 votes shraddha priya commented Apr 14, 2017 reply Follow Share @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)? 1 votes 1 votes Bikram commented Apr 16, 2017 reply Follow Share 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 0 votes 0 votes 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.