GATE CSE 2019 | Question: 37

Question

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

• A. $O(n)$
• B. $O(n \: \log \: n)$
• C. $O(n^2)$
• D. $\Omega (n^2 \log n)$

Comments

@Souvik33 bro i did’nt think this just 1 question will decide anythinng bcoz some questions are added to just waste student time and pressurise them .

---

@Ray Tomlinson yep bro you’re absolutely right, I was in this dilemma back then, but now I got into one 😊 so, one-two ambigous questions are not that big deal, you’ll get a MTA at the end if it’s a damm confusing question.

---

Given arrays: A1, A2, A3, A4, . . . . . . , An

Let their medians be: M1, M2, M3, M4, . . . . . ., Mn

For one list, using Median-of-medians quick select algorithm to find median it will take O(n) time.

For n such list, it will take O(n) * O(n) = O(n²)

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

TC = O(n²) + O(n)

�(

Answer 1

Given that  N is odd so median is m=(n+1)/2 now apply n times selection procedure (1 time each array, selection procedure is a quick sort algorithm only but take order n time to get correct element correct place .Note N is odd so median always be an array element ) so now we get all median of all array (since no. of array are still odd again apply previous procedure . you will get median of medians

Answer 2

Option (D) will be correct answer.

You need to sort all the $n^{2}$ numbers to get median of medians.

Those who have doubt, please find median of median of following 5X5 matrix in O($n^{2}$) complexity

$\begin{bmatrix} 13& 11& 6& 21& 1\\ 14& 7& 12& 2& 22\\ 23& 16& 8& 18& 3\\ 9& 19& 24& 17& 4 \\ 10& 20& 15& 25& 5 \end{bmatrix}$

 

If you first find the median of all the rows, and then find median of all the medians, you will get answer as 16.

But the correct answer is 13.

Comments

A/q To Me for sorting we will require "nlogn" time & we have "n" such arrays there so we will require  (n^2 logn) for the worst case.

Answer 3

Time taken to find the median of unsorted array with “n” elements is 0(n). Here there are total n^2 elemets, thus time taken is 0(n^2). Option C is correct

Answer 4

It is explicitly mentioned in the question Worst Case complexity.

Quick select algorithm which people are saying works in O(n) actually runs in O(n^2) if we consider the worst case (Pivot element is either smallest and largest), So worst case complexity becomes O(N^3).

Here, sorting and finding the median gives the result in O((N^2*logN)). Correct me if I am wrong or missed some point.