GATE CSE 2004 | Question: 40

Question

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among $\text{union, intersection, membership, cardinality}$ will be the slowest?

• A. $\text{union}$ only

• B. $\text{intersection, membership}$

• C. $\text{membership, cardinality}$

• D. $\text{union, intersection}$

Comments

Membership for an element checks whether it belongs to a given set or not.

I think what they're asking here is that given an element, we have to check it belongs any of the lists . This can be done by going through them once. Hence O(n1 + n2) time needed.

---

@Ayush Upadhyaya @Anu007....it is only possible when all element in list one less than list 2 as well as distinct....otherwise not possible

---

we cant use merge procedure for union or intersection because the individual sets are not sorted.. if they are sorted we can find union or intersection in O(n1+n2) time

Answer 1

Answer is (D).

Membership is linear search - $O(n_1 + n_2)$

Cardinality is linear - $O(n_1 + n_2)$

For union we need to ensure no duplicate elements should be present - $O(n_1 \times n_2)$ for each element we need to check if that element exists in other set

For intersection also for every element in set1 we need to scan set2 - $O(n_1 \times  n_2)$

Comments

For the union, why can’t we do it like this?

Insert the elements of L1 to a new list L3 one by one. Now, while inserting the element if it is found in L3 then it’s a duplicate value and we don’t need to insert it. Similarly, we do this for L2.

So total time complexity is : $T(n) =  \Theta(n1+n2) + \Theta(n)$

---

neel19

What is the time complexity for determining if an element exists in L3 in your algorithm? I think it is O(n). Hence time complexity of your algorithm is $O(n^2)$

 

EDIT: neel19

Please don’t hide your comments. Many people (including me) read comments after reading the answer. They help to clear many details related to the answer. Other people will never understand my comment without knowing what your question was

---

@anuracha

elements in intesection<=elements in union.

but option (a) has just union.that’s why (d).

Answer 2

Example

 List1:-> 3,2,6,8.  List2 :-> 5,6,2,8

Note:--(n1:-no. of elements in List1)

Membership:- is particular memeber is present in the set ot not.

Cardinality:- Size of set

For above operations single traversal of linked lists are enough so Linear time.O(n1+n2)

Union & Intersection:- take a new List3 of Size (List1+ List2) for union and min(List1,List2) for Intersection

For Union:--Copy List1 as it is into List3 now for each element of List2 scan List3 for duplicates so O(n1× n2). Copy only if it is not duplicate.

For Intersection:->>Take each element of L1 and scan in List2 for duplicates if avail then copy into List3. So here also O(n1×n2)

So clearly Union & Intersection is taking more time so it is slowest.

Hence Option D is Ans.

Comments

@reena_kandari  @Anu007

what you guys are mentioning is the time when the difference between the size of two list is large.

---

Good answer

---

very nice explanation rajesh sir

Answer 3

The set membership means “is an element of” so that the statement x∈A means that x is an element of the set A.

1. so for intersection once  go through all nodes of L1  and then of L2 and then serach for elements of both L1 and L2 in common  b/w two linked lists   print those 
2. for union same process as intersection BUT ,.. print all elements of L1 then those elemnts of L2 which were not in L1
3. CARDIANALITY is simple :count all nodes 
4. membership .. as above definition... traverse all nodes of L1 and L2 and look for a match 

So,final  answer is D

Answer 4

Only the union takes O(n1xn2) times where n1 is the number of elements in set A and n2 is the number of elements in set B the membership,intersection , cardinality takes linear time

Comments

intersection also takes O(n1*n2)..
if both n1 and n2 are sorted then Union/Intersection takes O(n) time.
if n1 qnd n2 not sorted then for each element in n1 compared with each element in n2. total n1*n2 comparison..
is it not ??

---

No i think if they are sorted then also for a element in one list...you have to check it in the other list for finding out duplicates.(by binary search)...so it will take nlogn time i guess..isn't it??

---

Binary search cannot be applied on a linked list..

---

@Bongbirdie who says Binary search cannot be applied on a linked list. binary search is possible on linked list but it takes O(n) every case.it is not efficient.linear search is better than binary search in linked list.