1,677 views
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.

2 Answers

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)
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.

No related questions found