edited by
1,563 views
3 votes
3 votes

1

edited by

3 Answers

1 votes
1 votes
Finding median of array A takes O(1)  time and same is for array B. Once we find both medians :

If Median (A) > Median (B) then find median of First half of A and Second half of B because these 2 portions contain the values between Median (A) and Median (B)

If Median (A) < Median (B) then consider Second half of A and First half of B for the same reason as above

In either case we are left with an array of size ($\frac{N}{2}$ + $\frac{N}{2}$) = N.

Now repeat the procedure for these half arrays then again for their halves until we are left with just 2 elements . The mean of those 2 numbers is the median of A U B

As the procedure has to be repeated for max LogN times the worst case time complexity would be O(logN). so ans is A
0 votes
0 votes
if we do AUB then it can or can not be sorted array so, sorting of AUB will take NlogN time in worst case. Once AUB is sorted then finding the median will take O(1) hence it will be O(NlogN)

answer should be (C)
0 votes
0 votes
Both A and B  are sorted array.

Merging of A and B takes O(n) times. [Applying merge algorithm of Merge sort]

Finding median takes O(1) times.

Answer is Option B. O(n).

Related questions

0 votes
0 votes
1 answer
2
1 votes
1 votes
2 answers
3
2 votes
2 votes
1 answer
4
yes asked Oct 6, 2015
1,329 views
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)