Let A1n and B1n be two arrays sorted in increasing order Ass

Let A[1..n] and B[1..n] be two arrays sorted in increasing order. Assume that both A and B have no duplicate elements. Write the pseudocode of an algorithm which computes A – B. More specifically the algorithms prints the elements which are in A and are not in B. The running time of the algorithm must be O(n).

Solution

Difference(A, B, n):
   int i=1, j=1

   while i<=n and j <= n:
       //since curren element if B is greater than current element of A
       // so we sure that A[i] is not in B because elements are sorted in both array
       if A[i] < B[i] then
           print A[i] // difference element
           i = i + 1
       // A[i] migth be in B so forward j
       else if A[i] > B[j]
           j = j + 1
       else // both are equal, so skip both elements
           i = i + 1
           j = j + 1

   // check whether some elements are left in A, that will be the part if difference(A- B)
   while i <= n then
       print A[i]
       i = i + 1

Time complexity: O(n + n) = O(n)