edited by
761 views
2 votes
2 votes

Two sets of numbers are given as sorted arrays in increasing order, A and B, with n and m numbers respectively. What is the best estimate for the complexity of computing the set A \ B? 

  1. $O(n.m)$
  2. $O(n^2 .m)$
  3. $O(n + m)$
  4. $(n log n + m log m)$
edited by

2 Answers

Best answer
2 votes
2 votes
I think A\B is an array of integers which is present in A but not in B.

To solve the given problem run the following code

Take another array C[n-1]

parameters i,j,k

i =0,j =0,k=0

A[ n] = ∞

and B[m] = ∞

while(i!=n)

  if (A[i] < B[j] )

     C[k] = A[i]

     i = i+1

     k = k+1

  end if

  if (A[i] ==B[j])

    i = i+1

 end if

 if (A[i] > B[j])

   j=j+1

end if

end while

So, the required array A\B = { C[0],C[2],..........,C[k-1]}

If you see the above code carefully it is a little modulation of merge algorithm of merge sort.

So, the time complexity is O (m+n)

which is option C.
0 votes
0 votes

If A\B means Elements present in A but not in B, the ans will be

O(nlogm) i.e. take every element of array A and do binary search in array B, hence n*log(m)

If A\B means Elements present in A but not in B or Elements present in B but not in A, then the ans will be

 O(nlogm + mlogn) i.e. take every element of array A and do binary search in array B,  and take every element of B and do binary search on A, hence n*log(m) + m*log(n)

Related questions

0 votes
0 votes
1 answer
1
Hakuna Matata asked May 23, 2018
1,136 views
What was the last rank in the waitlist group which got admission offer from IIT Kanpur last year?Is there any chance for waitlist rank of around 20?
1 votes
1 votes
1 answer
2
Hakuna Matata asked May 6, 2018
329 views
Are the admissions based solely on written & programming tests, or does GATE score get some weightage during final selection?