edited by
33,097 views
47 votes
47 votes

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 by

8 Answers

76 votes
76 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)$.
edited by
25 votes
25 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)

edited by
11 votes
11 votes

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

edited by
3 votes
3 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.
edited by
Answer:

Related questions

12 votes
12 votes
3 answers
3