GATE CS 2019 Q.47 (CS Q.37): Divide and Conquer

There are $n$ unsorted arrays: $A_1, A_2, \dots, A_n$ . Assume that $n$ is odd. Each of $A_1, A_2, \dots, A_n$ 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 $A_1, A_2, \dots, A_n$ is

$O(n)$

$O(n \log n)$

$O(n^2)$

$\Omega(n^2 \log n)$

Official answer and solution

Official answer: C
From: Official GATE 2019 answer key

Solution

Analyze the time required to find the median of each array and then the median of those medians.

We are given $n$ unsorted arrays $A_1, A_2, \dots, A_n$ , each of size $n$ with pairwise distinct elements.

Step 1: Compute the median of each array:
Using a linear-time selection algorithm (such as the Median-of-Medians / Quickselect algorithm), the median of an unsorted array of size $n$ can be found in $O(n)$ worst-case time.

Since there are $n$ such arrays, computing the median for all $n$ arrays takes:

n \times O(n) = O(n^2)\text{ time}

Step 2: Compute the median of the medians:
We now have a list of $n$ medians $M = \{m_1, m_2, \dots, m_n\}$ .
Finding the median of these $n$ numbers using the linear-time selection algorithm takes $O(n)$ worst-case time.

Total Time:

T(n) = O(n^2) + O(n) = O(n^2)

Final answer

Common trap

Sorting each array in O(n log n) time to find its median, which gives O(n^2 log n), forgetting that linear-time selection exists.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 47 of 65, printed as CS Q.37
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source