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

Please explain how to find median of Unsorted list in O(n) with n-elements

---

@ Sumit Rana 1 check https://stackoverflow.com/questions/10662013/finding-the-median-of-an-unsorted-array 

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

---

@Naveen Kumar 3 thanks i got it, didnt knew that method to find median

---

ans -> D

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.

---

when you say that you have all the medians one of each array than where are you going to store them because the question doesnot mention about space complexity?Do we assume infinite space in such a case??

---

Do we assume infinite space in such a case??

i will assume like that but i am not sure ! 

---

@Shaik

why u doing $O(n^{2})+O(n)$ and not $O(n^{2}).O(n)=O(n^{3})$

---

when you have doubt about is multiplication or addition, then think is it doing every time or one time ?

in this case after O(n$^2$) time i will do it one more time but not every time in the loop of O(n$^2$) time.

---

yes

and u r using here best case of quick select algorithm

right?

---

and u r using here best case of quick select algorithm

for getting best case in quick sort, we use find median but converse is not true ! 

---

@Shaik

I havenot got u

what u mean by "out sorting" ?

See we at first getting 1st median in $O(n^{2})$ time

then we perform a search on that array totally in $O(n)$ time to find 2nd median

but when u telling total time is $O(n^{2})$, isnot that mean, that 2nd median taken O(1) time??

---

Before finding 1st median, we cannot find 2nd median

For finding 1st median it takes $O(n^{2})$ time

then where is total time to find 2nd median?

---

Before finding 1st median, we cannot find 2nd median

For finding 1st median it takes O(n$^2$) time

who says ?

we can find median in O(n) time, but we have to know every median of n-lists ==> n*O(n) = O(n$^2$) time !

all medians are now in our hand !

---

@Shaik

all medians are now in our hand !

after that u have to select median again , and that could only be done in recursive procedure

So, after $O(n^{2})$ either it take some extra time to get worst case

or some other algorithm 

Say

50 45 40 35 30 25 20 15 10

51 46 41 36 31 26 21 16 53

52 47 42 37 32 27 22 17 54

48 43 38 33 28 23 18 13 8

49 44 39 34 29 24 19 14 9 

what will be median of median?

After getting all median, we again have to apply recursive call to get median of median

right?

---

We can sort the arrays is O(nlogn). We can find median of a sorted array in O(1) time. Then if we have have n such unsorted arrays, which we sort in O(nlogn) time, then the total time taken should be O($n^{2}$logn). Right?

---

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)???

---

@Shaik Masthan sir can you explain little bit more(using some example) about how we can find median in O(n)? 

Thanks

---

@halfcodeblood, refer the answer posted by @Tuhin Dutta

https://gateoverflow.in/302811/gate-cse-2019-question-37?show=303817#a303817

---

Now got it why not $nlogn$

---

@Akash 15

But the question asks for the worst case time and among all options nsquare logn is worst and we can get it with merge sort? So why option D is incorrect?

---

@Tushar Rana worst case means , worst case of best algorithm

---

@rishabh132 worst case means worst of best? Please provide me with something that provides more information on this. 

 

On wiki it says

In the case of running time, the worst-case time complexity indicates the longest running time performed by an algorithm given any input of size n, and thus guarantees that the algorithm will finish in the indicated period of time.

 

There's no mention of best algorithm. It's just an algorithm we are working with.

 

---

@Akash 15

How big omega tells anything about best case?

---

@Tushar Rana See, there can be multiple algorithms to solve this problem now we have to choose the best algorithm among them and have to find the worst case complexity of that algorithms...

For example, if you are given a sorted array and you have to find any element in that array, will you use linear search ? Not na.....

And what wikipedia is saying is about worst case complexity of AN algorithm, not problem...

---

@rishabh132

For finding element in a sorted array, we use the best algo that is binary search which gives logn time

So is this the worst case

or O(n) the worst case if we use linear search.

It solely depends on the method we are using.

And that doesn't make any worst case time any better. These both times logn and n are worst case time but it depends on searching method not the best algorithm we choose.

 
I am unable to understand how worst case complexity is different for an algorithm than for a problem?

---

@Tushar Rana Leave my earlier comment (sorry for the confusion).  See here if we want to compute median of median of an unsorted array then for n elements in one row it will take $O(n)$ now the thing is that even if we perform any other algorithm then the TC for the operaions may differ. If we use quicksort using pivot concept then the optimal worst case time complexity is $O(nlogn)$. But it is not about quicksort or any particular algorithm. The question focuses on median of median algorithm.
Once go through the wiki link: https://en.wikipedia.org/wiki/Median_of_medians
 

---

@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.