2 votes 2 votes Algorithms algorithms time-complexity + – Rock asked Jun 10, 2016 • retagged Jun 26, 2022 by makhdoom ghaya Rock 871 views answer comment Share Follow See 1 comment See all 1 1 comment reply Devshree Dubey commented Jun 12, 2016 reply Follow Share If the list has even or odd elements tat too does matter. 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes it is B. O(n).... debanjan sarkar answered Jun 11, 2016 • selected Apr 9, 2017 by rude debanjan sarkar comment Share Follow See all 7 Comments See all 7 7 Comments reply Rock commented Jun 11, 2016 reply Follow Share Please Explain... 0 votes 0 votes cse23 commented Jun 11, 2016 reply Follow Share in order to find median, array should be sorted. so, in worst case firstly we have to sort the array which takes o(nlogn) then finding the median will take o(1). hence total is o(nlogn) so (C)... 3 votes 3 votes Rock commented Jun 11, 2016 reply Follow Share But first U said its O(n).I m asking explanation for O(n) 0 votes 0 votes debanjan sarkar commented Jun 11, 2016 reply Follow Share http://www.cs.cornell.edu/courses/cs2110/2009su/Lectures/examples/MedianFinding.pdf 0 votes 0 votes debanjan sarkar commented Jun 11, 2016 reply Follow Share it can be done without first sorting refer http://www.cs.cornell.edu/courses/cs2110/2009su/Lectures/examples/MedianFinding.pdf 2 votes 2 votes alok_patel commented Oct 24, 2019 reply Follow Share In best case it is already sorted and using insertion sort it can be find out inin O(n) time . And further O(1) to find median. So overall complexity for best case could be O(n). 0 votes 0 votes toxicdesire commented Oct 25, 2019 reply Follow Share Check out order statistics. There's $O(n)$ algorithm for finding rank of an element in $O(n)$ in worst case. Median of medians. Hence, the answer is B. 0 votes 0 votes Please log in or register to add a comment.