Wednesday, April 8, 2009

How to perform UNION in O(1)

How do i perform UNION operation on two sets S1 and S2 such that the opearation takes O(1) time using a list data structure? 

this algorithm will take O(n) time
1)we will parse two lists completely , at the time time of parsing we will find out the max value among the sets ,
2) we will create a dummy array of max value size, 
3)again parse the list1 while parsing we will put 1 in the corresponding position(eg if 2 encounters array[2]=1) in the array, now parse the list2 now we will check the dummy array for that position if it is one delete that node repeat till last node of list2 
4)append the resulted list2 at the end of list1

This assumes that the two sets S1 and S2 are mutually disjoint. If they aren't, you will need to scan the lists which will cost O(n). 

I have this suggestion, What if modify the structure itself i.e.
struct node
int info;
int flag; // Each bit represents a list
struct node *next;

we maintain only ONE list huge list (the insertion n deletion will be very inefficient)
now the insertion algo is

insert(hugeList, info, listID)
search for info in the list
if not found then add new node
set flag = flag | listID

listID will be 1, 2, 4, ... and so on... depending on this value we will add a value to a list.

so if a node belongs to both list 1 & list 2 its flag will have a value 3 i.e. bit 0 & bit 1 set to 1
similarly if a node belongs to list 3 & list 1 flag will be equal to 5

now when we need to find the union of list 1 & list 2 (i.e. bit 0 or bit 1 set to true = 3)
we only need to print all elements such that (flag&3 !=0)
similarly for intersection we can check (flag & 3 == 3)

I hope the explanation was clear.
The union & intersection are O(1) in the sense we actually do not perform any union or intersection. They always exist. the catch is in accessing the elements of Union or intersection by using the flag bits.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.