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:
- O(n log(n))
- Ω(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?