Design an algorithm that given two lists of integers creates

Design an algorithm that, given two lists of integers, creates a list consisting of those integers that appear in both lists (each integer on the final list should appear only once). Describe your algorithm in terms of a high-level pseudocode focusing on main algorithmic tasks and not on low-level details. Analyze the running time of your algorithm. You will get full credit only if your algorithm achieves an asymptotically better worst-case performance than theta(n^2), where n is the sum of the lengths of the two input lists.

Solution

Algorithm 1:Using Hash

1)Create Empty List L to store Union of Lists

2)Create Empty Hash table H

3)Now take list L1 and travese it and put each element of it in Hash table H and List L.

4)Consider second List L2 do following:

For every element e in List 2 ...Search x in hash H .

If not in Hash put in Hash H and put it in List L.

5)Finally,print List L

Time complexity:(n+n) It is assumed that Hash table insert and search takes (1) time

Algorithm 2:Using Sorting

1)For this we need to sort both Lists.so use merge sort to sort them

2)Take two index variable for travesing two lists.Let it be i=0,j=0;

3)Let List L be final list.

4)if List1[i] <List2[j] then insert in List L.Increment i

5)if List1[i] >List2[j] then insert in List L.Increment j

6)2)if List1[i] ==List2[j] then insert any one of them in List L.Increment i as well as j.

7)Print the remaining elements of Larger List.

Time Complexity: O(nLogn + nLogn).= O(nLogn).

In this case we are using merge sort so that we need O(nLogn + nLogn) time to sort both lists.

Also we need O(n) to traverse List.Hence Overall time complexity is  O(nLogn)

Algorithm 3:Using sorting and searching

1) Initialize List L as empty.
2) Find smaller of List L1 and List L2 and sort the smaller array.
3) Copy the smaller array to List L.
4) For every element e of larger array, do following
Binary Search e in smaller array. If e is not present, then copy it to L.
5) Print List L

Time complexity:O(nLogn).As we are using binary search on every element of List.Hence O(Logn) for Binary Search and O(n) for traversing each element of List