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

Finding Median(or any other value at a given index in corresponding sorted array) in unsorted array in O(n), 

---

@sohamm20

We are not concerned with sorting the array here. Finding the median is a different problem altogether and in fact it can be done deterministically in O(n) time by following the Median of Medians algorithm. There does exist a similarity with regard to Quicksort i.e finding the optimal pivot element. Why do we care about the pivot element to land at the middle ? Because then we have found the median ! 

So, the real question boils down to - Can I find the median in a more efficient time than O(nlogn) (which is the time to efficiently sort an array and then find median which is simply mid point of the sorted array) .

 There are two algorithms to find median in unsorted array - Quickselect which finds the median in O(n) time in average case and is easier to understand. We randomly select a pivot element just like Quicksort , then partition the set into left and right halves. 

• If the selected pivot equals the middle index , the median was found.
• If selected pivot lies way to the right, we overshot the median and must look for it in the left half.
• If the selected pivot lies way to the left, we have to travel further to the right to get to the median position and hence must look for it in the right half.

We just reduced the problem size by half ! This is the difference with Quicksort where we need to recursively solve both halves but here we discard the unfavorable half which cannot contain the median. So recurrence becomes :

     

           T(n) = n + n/2 + n/4 + n/8 + ... = n*1/(1-1/2) = 2n = O(n)

 

Thus finding median is O(n) algorithm ! But there is a catch here. We chose the pivot randomly and just like the Quicksort case, our choice could be bad which could partition the array into heavily unbalanced halves. In that case, the Quickselect algorithm would have a worst case time complexity of O(n^2). And it is this problem that the Median of Medians algorithm is trying to solve - to deterministically find the pivot in O(n) time such that it splits the array into two equal halves and hence that pivot is the median.

---

thanks @petals90. it's clear now

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

@Akash 15

Yes that's something I can definitely agree upon. It's not about algorithm that gives worst case time complexity. Because then answer should be D. They should definitely need to properly define this that what they were asking for. Maybe include using "pivoting technique what's worst time for medians of medians". 

---

Medians of median method helps to get median of unsorted array in O(n)

---

thanku

 

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. :)

---

Thank you bhaiya for awesome resources.

 

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.

Answer 5

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 6

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.