+2 votes
4k 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 | 4k views
+6

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/

## 6 Answers

+13 votes

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)

by Veteran (60k points)
edited
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).
0

@Harsh Kumar You are right , Indian education is totally scrap.  Even studying for Gate is mostly useless. As student with Computer Engineering  Degree I am expected to do coding not just as my work but as fun even after office hours, but what I am doing? I am solving MCQ's.

I really think life of engineers in India would be far better if there were no IIT system in India then people like us would focused solely on our skills rather that clearing entrance exam of so called elite institutes which don't even stand in top 100.

As most of our's parents can't afford sending us abroad for ms , only way us to get good education(and not best) education is to prepare for exams like this even if it feels totally weird sometime.

0

@mehul vaidya Yes, it is the worst education system -- because it makes students think that solving MCQs is the way to clear GATE :)

+8 votes
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$).
by Veteran (61.9k points)
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?

+2 votes
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.
by Active (2.5k points)
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.
by (35 points)
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.
0 votes
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
by Junior (903 points)
0 votes

Ans C)

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

by Loyal (9.2k points)
edited
Answer:

+6 votes
3 answers
1
+3 votes
5 answers
2
+3 votes
8 answers
3
+4 votes
4 answers
4
+1 vote
5 answers
5
+2 votes
4 answers
6
+1 vote
7 answers
7