GATE CS 2019 Q37 — Asymptotic Worst Case Time and Space Complexity

To find the median of the medians of $n$ unsorted arrays $A_1, A_2, \dots, A_n$, each containing $n$ distinct elements, we can break the process down into two main steps:

1. Find the median of each individual array:

   Each array $A_i$ is unsorted and has $n$ elements. The median of an unsorted array of size $n$ can be found in $O(n)$ worst-case time using a linear-time selection algorithm (such as the Median of Medians algorithm).

   Since there are $n$ such arrays, the total time required to find the medians of all $n$ arrays is:

   $$n \times O(n) = O(n^2)$$
2. Find the median of the computed medians:

   Let the medians of the $n$ arrays be $m_1, m_2, \dots, m_n$. This is a set of $n$ elements. Finding the median of these $n$ elements takes:

   $$O(n) \text{ time}$$

Total Worst-Case Time Complexity:

Combining both steps, the overall worst-case time complexity is:

Hence, the correct option is C.