GATE CSE
First time here? Checkout the FAQ!
x
0 votes
427 views

P.S. Applied conditions given in " " is applicable on any(as per choice)

asked in Programming by (157 points) 2 4 9 | 427 views

2 Answers

+2 votes
then the complexity will be O(a+b) because merge procedure isnt in place . And the comparisons required is min of a,b .
answered by Boss (9.8k points) 10 36 103
edited by
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.
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?
Yes. Exactly.
Sir what about that min(a,b)?
After min(a,b) comparisons, one array will be finished and then there won't be any more comparisons.
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?
sorry, n means a+b.
I GOT IT SIR ! thanx i was confused with it

@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.

 

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
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..
answered by Veteran (32.9k points) 45 230 468
yes. But time complexity would include copying too.
yes time complexity will be O(n) only
will the no of comparisions remain min(a,b) even when we use setinel node(infinity)??
@pooja palod O(n) means (comparison+shifting both array into new array) max(a,b)+O(a)+O(b) right??


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23242 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7096 Points

  4. srestha

    6012 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4928 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4278 Points

  9. sushmita

    3954 Points

  10. Rishi yadav

    3744 Points


Recent Badges

Popular Question Ml_Nlp
Notable Question set2018
Notable Question rahul sharma 5
Notable Question Sanjay Sharma
Notable Question Lakshman Patel RJIT
Popular Question makhdoom ghaya
Popular Question Çșȇ ʛấẗẻ
Reader kenzou
Popular Question mystylecse
Notable Question Sanjay Sharma
27,262 questions
35,076 answers
83,760 comments
33,185 users