Time complexity to find Median of Medians

Question

I recently wrote my Grad school Admission test few days back and the following question appeared in the test.
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 medians of A1, A2, ..., An is:

1. O(n)
2. O(n log(n))
3. O(n^2)
4. Ω(n^2 log(n))

Approach 1: Compute the median using Counting Sort for all arrays and then store the median values in a separate array. Once again apply Counting Sort on the newly created array having median values and compute the median. Time Complexity = O(n^2) Space Complexity = O(n)

Approach 2: Instead of Counting sort, use any other algorithm with constant space complexity, thereby yielding a total Time complexity of O(n^2 log(n)).

According to space-time trade-off, a problem or calculation can either be solved in less time by using more storage space (or memory), or by in very little space by spending a long time.

Approach 1 favours time and Approach 2 favours space. I believe that space should be favoured as the size of Array will be very high on performing Counting sort when the range of values is high. Thus I marked Ω(n^2 log(n)) in test. However, my mentor and one my acquaintances say time should be favoured and O(n^2) is the correct answer. So, my question is whether to favour time or space?

Answer 1

The running time of counting sort isn't $O(n)$, in general. If you are guaranteed that every element of the array is an integer in the range $1..n$, then the running time of counting sort is $O(n)$; but if you aren't guaranteed that, in general the running time could be much worse.

Since the question doesn't make any guarantees that the elements of the array will be in a specified range, you can't claim that counting sort will have $O(n)$ running time, and your analysis of Approach #1 is not correct.

Approach #2 does indeed provide an algorithm with running time $O(n^2 \log n)$. However, that's not the best algorithm. There are better algorithms, which can find the median in $O(n)$ time. So, the correct answer is $O(n^2)$ ... but not for any of the reasons listed in your question. See https://en.wikipedia.org/wiki/Selection_algorithm and Find median of unsorted array in $O(n)$ time.