0 votes 0 votes P.S. Applied conditions given in " " is applicable on any(as per choice) Programming in C algorithms sorting + – Saurabh Gupta 1 asked Jul 28, 2015 Saurabh Gupta 1 2.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes then the complexity will be O(a+b) because merge procedure isnt in place . And the comparisons required is min of a,b . Pranay Datta 1 answered Jul 28, 2015 • edited Jul 28, 2015 by Pranay Datta 1 Pranay Datta 1 comment Share Follow See all 23 Comments See all 23 23 Comments reply Arjun commented Jul 28, 2015 reply Follow Share Complexity or no. of comparisons? 0 votes 0 votes worst_engineer commented Jul 28, 2015 reply Follow Share Hi @Arjun sir , I think complexity will be O(n) . 1 votes 1 votes Pranay Datta 1 commented Jul 28, 2015 reply Follow Share both . 0 votes 0 votes Arjun commented Jul 28, 2015 reply Follow Share All the elements must be moved to the new array rt? 0 votes 0 votes Pranay Datta 1 commented Jul 28, 2015 reply Follow Share oops ... :P yeah right , i was considering it like link list . anyways comparisons is min of a,b right ?? 1 votes 1 votes Arjun commented Jul 28, 2015 reply Follow Share Yes. 0 votes 0 votes debanjan sarkar commented Jul 29, 2015 i edited by debanjan sarkar Jul 29, 2015 reply Follow Share @Arjun Sir,Sir but here no comparisons will be required as it is given that "one array smallest element is greater than the largest element of other one".We have to just copy the elements into a new array...is this correct sir? 0 votes 0 votes debanjan sarkar commented Jul 29, 2015 reply Follow Share @Arjun Sir,Sir and coming to number of comparisons...Sir, the worst case number of comparisons to merge k elements from two lists is k-1...hence if the condition would not had been here...then here number of comparisons in worst case would have been a+b-1.....Sir, please clarify this statement. 0 votes 0 votes Arjun commented Jul 29, 2015 reply Follow Share one array smallest element is greater than the largest element of other one This is a property of the input we don't know, and we need min(a, b) comparisons to identify this property it self. For normal merge, n-1 comparisons is correct. 0 votes 0 votes debanjan sarkar commented Jul 29, 2015 reply Follow Share Sir please explain the min(a,b) part once again....(my confusion is in the part that when the property is already given why should we search for the property? and if so how min(a,b) is assuring that? we could have compared the 1st element of one array with last element of other and the 1st element of other array with the last element of the first array to assure the property...hence 2 comparisons are enough to assure the property....) Sir please explain this one.. 0 votes 0 votes Arjun commented Jul 29, 2015 reply Follow Share Then why does quick sort take $O(n^2)$ complexity when the given array is sorted? 0 votes 0 votes debanjan sarkar commented Jul 29, 2015 reply Follow Share Sir because the input can be anything we dont know it prior.....but here it is saying that the input is always given with that property... 0 votes 0 votes debanjan sarkar commented Jul 29, 2015 reply Follow Share but if we dont know the input prior then how min(a,b) comparison assures the property? we could have compares the first and last elements of both the array...?? 0 votes 0 votes Arjun commented Jul 29, 2015 reply Follow Share If input is always given like that then you are right- but that is not the question- it is telling only for a particular input- merge algorithm is designed without this knowledge. And you are right in 1 comparison to identify the property- but then we have to modify the standard merge procedure to do this. 1 votes 1 votes debanjan sarkar commented Jul 29, 2015 reply Follow Share Ok i got it sir..that means there will be no such benefit if this condition holds for one such input....the merge procedure still remains O(n)...isnt it sir? 1 votes 1 votes Arjun commented Jul 29, 2015 reply Follow Share Yes. Exactly. 1 votes 1 votes debanjan sarkar commented Jul 29, 2015 reply Follow Share Sir what about that min(a,b)? 0 votes 0 votes Arjun commented Jul 29, 2015 reply Follow Share After min(a,b) comparisons, one array will be finished and then there won't be any more comparisons. 0 votes 0 votes KOUSHIK commented Apr 11, 2016 reply Follow Share sir, i can't understand that how O(n) as there is no mention about total size of both array as n rather than a+b . I got other explanations.can you please help me out? 0 votes 0 votes Arjun commented Apr 12, 2016 reply Follow Share sorry, n means a+b. 0 votes 0 votes KOUSHIK commented Apr 12, 2016 reply Follow Share I GOT IT SIR ! thanx i was confused with it 1 votes 1 votes vijaycs commented May 12, 2016 reply Follow Share @Arjun Sir, Suppose array A has "a" elements and array B has "b" element and a>b And if b[0] >a[0] then in this case no. of comparison would be 'a' times. I think in the best case no. of comparison = min(a,b) And in the worst case no. of comparison = max(a,b) Please tell me sir where I am wrong. 0 votes 0 votes moin commented Mar 7, 2017 reply Follow Share O(a+b) is the right answer as number of comparison required is min(a,b) but we need to take the time of copying the remaining elements of larger list into the final list thats why time complexity is O(a+b) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes if one array smallest element is greater than largest element of other one comparisons will be min(a,b)...this would be best case for merge procedure..one array would become empty so we can copy elements of another array.. Pooja Palod answered Aug 3, 2015 Pooja Palod comment Share Follow See all 4 Comments See all 4 4 Comments reply Arjun commented Aug 3, 2015 reply Follow Share yes. But time complexity would include copying too. 0 votes 0 votes Pooja Palod commented Aug 3, 2015 reply Follow Share yes time complexity will be O(n) only 0 votes 0 votes sushmita commented Nov 30, 2016 reply Follow Share will the no of comparisions remain min(a,b) even when we use setinel node(infinity)?? 0 votes 0 votes learner_geek commented Aug 11, 2017 reply Follow Share @pooja palod O(n) means (comparison+shifting both array into new array) max(a,b)+O(a)+O(b) right?? 0 votes 0 votes Please log in or register to add a comment.