3 votes 3 votes Algorithms algorithms time-complexity sorting test-series + – Himanshu1 asked Dec 16, 2015 • edited Jul 17, 2022 by makhdoom ghaya Himanshu1 1.6k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Sandip Shaw commented Dec 16, 2015 reply Follow Share Option C? 0 votes 0 votes Umang Raman commented Dec 16, 2015 reply Follow Share http://www.geeksforgeeks.org/median-of-two-sorted-arrays/ 3 votes 3 votes Rajesh Jaiswal commented Nov 6, 2016 reply Follow Share option A is correct because without merging (union) both array median can be obtain in O(logn) 0 votes 0 votes Please log in or register to add a comment.
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 Heisenberg answered Mar 23, 2017 Heisenberg comment Share Follow See all 0 reply Please log in or register to add a comment.
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) cse23 answered Jun 4, 2016 cse23 comment Share Follow See all 2 Comments See all 2 2 Comments reply Himanshu1 commented Jun 5, 2016 reply Follow Share nopes, answer is (A). 1 votes 1 votes hkcgate2017 commented Sep 2, 2016 reply Follow Share ans c is correct ........see A &B are sorted arr right A U B will might be unsorted...then sort them O(nlogn) and find median O(n) T(n)=O(nlogn)+O(n)=O(nlogn) 0 votes 0 votes Please log in or register to add a comment.
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). Arnab Bhadra answered Mar 23, 2017 Arnab Bhadra comment Share Follow See all 0 reply Please log in or register to add a comment.