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 all lists are unsorted !

therefore we can't apply Binary search,

one way to find median is sorting the list, it takes $Θ(n logn)$, But with out sorting we can find median in $O(n)$.

For one list it takes $O(n)$, then for n-lists it takes $O(n^2)$.

So, now median of every list in our hand !

note that these medians are also not sorted !

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

$TC = O(n^2) + O(n) = O(n^2)$.

Comments

yes @Krithi00 

---

IN answer he mentioned about Binary Search is not applicable, let say if list was sorted then also what you do binary search for, in that case to find median you would just take out middle element

---

How do you get the time complexity of finding the median of a sorted array is 0(nlogn)???

Answer 2

Here is the pseudo code for finding median in linear time. For proof ref this.

    
FindMedian(A,k){
    if (A has 10 or fewer elements){
        sort A
        return A[k-1]
    }
    partition A into subsets S[i] of five elements each
       (there will be n/5 subsets total).

    for (i = 1 to n/5)
       x[i] = FindMedian(S[i],3)
    M = FindMedian({x[i]}, n/10)

    partition A into A1<M, A2=M, A3>M
    if (k <= length(A1))
        return FindMedian(A1,k)
    else if (k > length(A1)+length(A2))
        return FindMedian(A3,k-length(A1)-length(A2))
    else return M
}

 

1. For each row find median $M_i$ using FindMedian algorithm. $\forall\ i\  M_i \in M$
2. Find median of $M$

Time complexity:

1. Total n elements in each row so finding median of a row will take $O(n)$ time. Total $n$ row so total time $n*(O(n)) = O(n^2)$
2. $|M| = n$ so finding median of $M$ will take $O(n)$ time.

Total time $=O(n^2)+O(n)=O(n^2)$

Answer is (C)

Comments

SO, what is the answer, sir ?

---

yeah, what should be the answer?

---

Update answer of this question.. It is still showing as option C

---

@Digvijay Pandey

The worst case time complexity is asked. But in option 4, they have used big Omega notation which says about best case complexity.

So assuming extra space is allowed C is the best choice here.

---

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.

---

But they have asked median of medians which is 16 only

---

I fail to comprehend how the HELL will any GATE aspirant go and search for all such nooky links all over the internet while preparation?

Shouldn't it be the case that there should be a more formal and standard approach for solving such questions?

If some competitive programmer sits and finds the solutions to such problems, maybe he/she be able to find an even better solution using some weird tricks...!!

Will the GATE authority then entertain such an approach taken by the competitive programmers...?

 

I AM SIMPLY FED UP WITH NONSENSE INDIAN EDUCATION SYSTEM....!!!

---

@Harsh Kumar, You may also get the same information in the chapter "Medians and Order Statistics"  in "Introduction to algorithms" by Cormen et al. The first page of this chapter mentions that given n distinct elements (as also given in the question ) the median can be found in O(n) .

 

Quoting from Cormen: "We conclude that we can find any order statistic, and in particular the median, in expected linear time, assuming that the elements are distinct."

---

Yes. Everything is in standard books. Just that one needs to read and understand properly. Of course Indian education system is at fault because 95% of faculties do not deserve to be teaching -- you can ask them to give GATE and see if they'll qualify 😊

---

I agree. People are only studying what these random coaching institutes teach and then they complain . Best is to cover the standard books and follow NPTel and other IIT Lectures.  And as a consequence we will face less difficulties when we finally get admitted to these IITs and IISc.

---

Of course Indian education system is at fault because 95% of faculties do not deserve to be teaching

is students encouraging those teachers or teachers creating those students ?

in my final year (2016), i want to write gate,  started preparation in october, after preparing TOC 20 days i got 8-10 doubts ( including GATE questions ), i took them to my HOD who taught me the TOC subject in my academics, he took 15-20 mins to each question, and said this is not that much important, just left it for all the questions !   then i understood i wasted 2-hours !!

after i read CN, went to the lecturer who taught me, same thing again repeated !

after i read Graph Theory... again HISTORY repeats !!!

i left the preparation itself ! directly went to the EXAM, got 41.2 marks ( i know this is not good. )

i am not only blame the system only, i am also blaming the students ( including me ) who doesn't even try to think about other resources. and getting 80% ( 95% of the questions which taught in class only and doing 1-day batting ) in BTech is more than enough !

---

@subhrob Actually, I had left that topic totally. I thought this chapter of Cormen was not in the syllabus and so when the question was asked, I did solve it using my intuition. My bad. I should've studied that chapter also.

@Ahabnnc Dear, I did not attend any coaching center in my entire life and neither will I do ever. To clarify stuff, I did qualify for JEE advanced (approx 8000 rank) using only standard books and self-study (I might sound rude here, but I am deeply sorry). I am not complaining, but rather telling the extended truth. It was only this time that I did ignore this topic (my bad) and lost 2.67 marks thanks to my ignorance.

Thank You.

---

Harsh,

My answer was in no way pointed at you. I just said what I feel and wats true. I dont know you. You colud be the topper of JEE with rank 1. It wasnt meant to insult you or any other great mind here. Please never ever consider yourself so important that people will talk about u. Never take things to yourself

---

Complexity of median of medians in wikipedia O(nlogn)

https://en.wikipedia.org/wiki/Median_of_medians

---

mam, where it written in wiki ?

---

Median of medians can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O(n log n). 

 

---

"Median of medians can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O(n log n)"

This O(nlogn) is worst case complexity of QuickSort if you are using Median of medians concept.

Complexity of Median of medians in O(n) only.

---

Say, median of every array are

4,6,1,7,8,2,3

Now, after finding median i.e. $O(n^{2})$, u have to go for selection algo to find median of median, which works for O(n/2) times

So, $O(n^{2}).(n/2)$=$O(n^{3})$

isnot it??

---

it means, By choosing median as pivot, Quicksort behaves O(n.logn) but it doesn't mean median of medians find in O(n.logn).

---

@Harsh Kumar You are right , Indian education is totally scrap.  Even studying for Gate is mostly useless. As student with Computer Engineering  Degree I am expected to do coding not just as my work but as fun even after office hours, but what I am doing? I am solving MCQ's. 

I really think life of engineers in India would be far better if there were no IIT system in India then people like us would focused solely on our skills rather that clearing entrance exam of so called elite institutes which don't even stand in top 100.

As most of our's parents can't afford sending us abroad for ms , only way us to get good education(and not best) education is to prepare for exams like this even if it feels totally weird sometime.

---

@mehul vaidya Yes, it is the worst education system -- because it makes students think that solving MCQs is the way to clear GATE :)

---

Selection algorithm gives $O(n)$ in average case, but question asks us result in worst case, which is $O(n^{2})$. So wouldn't the worst case for finding median in $n$ arrays be $n\times O(n^{2})=O(n^{3})$?

---

Just a small counterpoint for those discussing the Indian education system which I have come to understand 6 years after graduation: getting into private tier-3 colleges was a result of our poor entrance prep, and thus was our choice. And not remaining competitive atleast with those in IITs and other elite Indian institutes, if not foreign institutes, was also our choice. We are the choices we make.

---

Is studying for GATE waste of time then?, should I join a job instead ?

---

@srestha , I also think that it should be O(n^2 logn).

Can you please explain how are people saying that finding median of an array with n elements will take O(n) ;

 

---

Explaination of above alogrithm

 

This code is an algorithm to find the median of an array 'A' in an efficient way, where the median is the middle value of the sorted array. The code divides the problem into smaller subproblems until it can easily find the median.

Let's break down the algorithm step by step:

1. If the array 'A' has 10 or fewer elements:
   - The code sorts the array 'A' in ascending order.
   - Then it returns the element at the (k-1)th index, which is the kth smallest element in the sorted array.
   - This works because in a sorted array, the element at index k-1 will be the kth smallest element.

2. If the array 'A' has more than 10 elements:
   - The code partitions the array 'A' into subsets 'S[i]' of five elements each. If there are any remaining elements, they form a subset as well.
   - For each subset 'S[i]', the code finds the median by selecting the middle element (element at index 3 when sorted).

3. Next, the code finds the median 'M' of all the medians found in the previous step.
   - It creates an array 'x[i]' containing all these medians.
   - Then it recursively applies the same algorithm to find the median 'M' of this new array 'x[i]'.

4. The array 'A' is then partitioned into three parts based on the median 'M':
   - Elements less than 'M' are put into 'A1'.
   - Elements equal to 'M' are put into 'A2'.
   - Elements greater than 'M' are put into 'A3'.

5. Finally, the algorithm checks where the desired median 'k' lies relative to the sizes of 'A1' and 'A2':
   - If 'k' is less than or equal to the length of 'A1', then the algorithm recursively finds the median in 'A1'.
   - If 'k' is greater than the combined length of 'A1' and 'A2', then the algorithm recursively finds the median in 'A3'.
   - Otherwise, the median 'M' is returned since it means 'k' lies within 'A2'.

The algorithm keeps breaking down the problem into smaller subproblems until it finds the desired median. By doing so, it ensures that it doesn't have to sort the entire array, making it more efficient than a standard sorting-based approach for finding the median.

Answer 3

Ans C) 

REF: https://rcoh.me/posts/linear-time-median-finding/

O(n) for finding median in 1 list. Now for finding median for n lists we need O($n^2$)

Comments

Thank u finally a worthy one!!

---

Awesome @Tuhin Sir. Finally a good explaination. :)

Answer 4

Nothing is mentioned about using extra space or not. So simplest solution is to copy all the arrays to a larger array of size n^2.

Now run median of medians algorithm upon the larger array which would take O(n^2) time.

Space complexity = O(n^2) + O(log n^2)

Option D is not correct as it is saying about best case time complexity but they have asked about worst case time complexity.

Best choice option C.