Question

There are n unsorted arrays: a1, a2, ..., an. Assume that n is odd. Each of a1, a2, ..., an contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of a1, a2, ..., an is

Answer 1

Answer:

Given that all lists are unsorted !

therefore we can't apply Binary search,

one way to find median is sorting the list, it takes Θ(n logn), But with out sorting we can find median in O(n).

For one list it takes O(n), then for n-lists it takes O(n2).

So, now median of every list in our hand !

note that these medians are also not sorted !

Therefore make all these medians as one list, then with in O(n) time we can find the median of medians.

TC = O(n2) + O(n) = O(n2).