Question

Let A = {a1, . . . , ak} and B = {b1,. . . , bm} be two sets of numbers. Consider the problem of finding the difference set of A and B(A–B), i.e., the set of all elements of A that are not elements of B.

a)Design a n O(nlogn) algorithm for solving this problem.

b)Show that the worst-case complexity of your algorithm is O(n logn)

Answer 1

Solution

Part 1

A = {a1, . . . , ak} and B = {b1,. . . , bm}

The required algorithm is given below:

• Elements of set A are stored in array A. If set has k elements the index of first element in array A is 0 and the index of the last element is k-1
• Elements of array B are stored in array B. If set has m elements the index of first element in array B is 0 and the index of the last element is m-1
• Array B is sorted using merge sort.
• Scan array A one element at a time starting from index 0 and corresponding to each element in A, a binary search is performed in array B.
• If the binary search is succesful ,the element will not be present in A-B.
• If the binary search is not successful the element is present in A but is not present in B. So it is present in A-B . Print the element

Part 2

Consider array A has k elements and array B has m elements.

Sorting the elements of array B using merge sort results in mlog₂m time complexity.

Corresponding to each element of array A a binary search is performed in array B.

Binary search of a single element in an array of size m takes log₂m complexity.

So for all the elements of array A, total time complexity due to binary search is k*log₂m

Hence total complexity = mlog₂m + k*log₂m

For the problem lets consider both array A and array B has n elements each.In this case sorting of array B results in nlog₂n complexity. And the binary search of n elements of array A in array B one by one results in n * log₂n complexity.

So total complexity = nlog₂n + nlog₂n = 2nlog₂n = nlog₂n = O(nlogn)