IIT Kanpur

Question

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? 

• A. $O(n.m)$
• B. $O(n^2 .m)$
• C. $O(n + m)$
• D. $(n log n + m log m)$

Comments

what is mean by \ symbol.??

---

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[1]..........,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.

---

same as this https://gateoverflow.in/2603/gate1995_1-16

just in place of A+B, they asked A-B

---

Thank you :)

---

@Kushagra Chatterjee

In case if A={6,7,8,9,10},  B={1,2,3,4,5}, then for all values A[I]>B[j], so j will increment upto m, and it will come out of while without putting anything in C, however here C should have had entire A, isn't it? I think this thing must be handled, please correct me if I am wrong

---

Thanks a lot for pointing out the mistake. Edited my answer. Please check it again.

---

Yeah it seems to be good, thanks!

Answer 1

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.

Comments

In case A[i]=B[j]. then increment should be done on both i  and j

---

I think there will be no problem if we increment i alone can give me an example where it would be a problem.

---

It won't be a problem. Because if these are  equal and you increment only i, then in next iteration data at j will be less than i and j will be incremented. But it is best practice to complete current iteration work in current iteration only. Why do we want to take an extra iteration just to increment j? Anyways just a suggestion, your program is correct though :)

Answer 2

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)

Comments

The answer is C

O(m+n)