+1 vote
3.1k views

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

1. $O(n)$
2. $O(n \: \log \: n)$
3. $O(n^2)$
4. $\Omega (n^2 \log n)$
edited ago | 3.1k views
+5

i think it should be O(n^2) because to find median it takes O(n). time using partition algo. so O(n^2) for finding medians of all arrays. plus O(n) time for again finding median of medians so total time = O(n^2) + O(n) = O(n^2).      ref. ;- finding median of unsorted array https://discuss.codechef.com/questions/1489/find-median-in-an-unsorted-array-without-sorting-it

https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

Here is 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)$

edited
0
SO, what is the answer, sir ?
0
yeah, what should be the answer?
0
Update answer of this question.. It is still showing as option C
0

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

0
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.
0
But they have asked median of medians which is 16 only
+2
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....!!!
+2

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

+6
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 😊
+1
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.
+2

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 !

0

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

0
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
0

Complexity of median of medians in wikipedia O(nlogn)

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

0
mam, where it written in wiki ?
0

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

0

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

0
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??
0
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).
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$).
0
Please explain how to find median of Unsorted list in O(n) with n-elements
0
+1

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

0
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.
0
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??
0

Do we assume infinite space in such a case??

i will assume like that but i am not sure !

0
@Shaik

why u doing $O(n^{2})+O(n)$ and not $O(n^{2}).O(n)=O(n^{3})$
+1
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.
0
yes

and u r using here best case of quick select algorithm

right?
0

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 !

0
@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??
0
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?
0

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 !

0

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

+1 vote
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.
edited
+1 vote
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.
0
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.
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

Ans C)

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

edited

1
2