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

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.