0 votes 0 votes What is the complexity of finding median of medians of N lists containing N elements each. N is odd and the lists are unsorted and no 2 lists have same element. xariniov9 asked Feb 3, 2019 xariniov9 1.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply SagarGaddam commented Feb 3, 2019 i edited by SagarGaddam Feb 4, 2019 reply Follow Share O(n^2) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes O(n^2) As per the options, as they were all in Big O, so I took worst i.e. O(n^2) Markzuck answered Feb 3, 2019 Markzuck comment Share Follow See all 4 Comments See all 4 4 Comments reply Bibhu Pala commented Feb 3, 2019 reply Follow Share To sort : n log n And for n such arrays n * n log n i.e n^2 log n 1 votes 1 votes Aman Juyal commented Feb 3, 2019 reply Follow Share I think is O(N^2) because apply n times selection procedure as median is (n+1)/2 (given that n is odd) so we get n medians of median now again aplply selection procedure so O(N) so net time complexity is O(N^2) correct me if i am wrong 0 votes 0 votes Verma Ashish commented Feb 3, 2019 reply Follow Share @Aman lists are unsorted.. 0 votes 0 votes xariniov9 commented Feb 3, 2019 reply Follow Share Selection algorithm is for unsorted lists. It is randomised algorithm and takes O(n) time to find k'th smallest element. Specifically for this case, k=(n+1)/2. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Median can be found in O(n) using randomised partition for 1 list. For n lists it is n*n, so I think O(n^2) is the answer. xariniov9 answered Feb 3, 2019 xariniov9 comment Share Follow See all 3 Comments See all 3 3 Comments reply Markzuck commented Feb 3, 2019 reply Follow Share but isnt it like if O() is asked then always the max among the options? 0 votes 0 votes xariniov9 commented Feb 3, 2019 reply Follow Share No, that is not required. Generally we take the tightest upper bound. Theoretically O(n^2) is subset of O(n^2log n). 1 votes 1 votes Markzuck commented Feb 3, 2019 reply Follow Share So what should be the final answer as per you? @xariniov9 coz n2logn looks correct for sure. 0 votes 0 votes Please log in or register to add a comment.