2 votes 2 votes Algorithms algorithms time-complexity + – Rock asked Jun 10, 2016 retagged Jun 26, 2022 by makhdoom ghaya Rock 785 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 Show 4 previous comments 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.