retagged by
711 views

1 Answer

0 votes
0 votes

We have three case here.

1.First copy the element in new array and sort it and find median which will take O(2n(lon2n) time.

2.Second merge two sort array each of size n will take O(n+n) time and then find median.

3.Third case optimal we can simply do by comparing medians

Let see the algorithm,

median(int a1[] ,int a2[] ,int n){

int m1=median (a1,n);

int m2=median (a2,n);

if(m1=m2)

{

return m1;

}

if(m1<m2)

{

return (a1+n/2 ,a2,n-n/2);

}

else

{

return (a2+n/2 ,a1, n-n/2);

}

}

Which will take O(log n) time .

Related questions

1 votes
1 votes
1 answer
2
go_editor asked May 31, 2016
686 views
Let $G = (V, E)$ be an undirected weighted graph with all edge weights being positive. Design an efficient algorithm to find the maximum spanning tree of $G$.
14 votes
14 votes
2 answers
3
go_editor asked May 31, 2016
1,629 views
Let $H_1$ and $H_2$ be two complete binary trees that are heaps as well. Assume $H_1$ and $H_2$ are max-heaps, each of size $n$. Design and analyze an efficient algorithm...