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

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

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.