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

Union would be like, create a new LL set3, insert all elements from set1.

For each element in set2, check if exists in set1, if not insert in set3

---

Even though answer id D.
Isn't intersection will be faster than Union.
Let's take n₁ as no. of input in one linklist and n₂ as no. of input in second linklist.
if n_i is no. of nodes need to be created for intersection and n_u is no. of nodes nedd to be created for union
then-
0 <= n_i <= min(n₁ , n₂ )
max(n₁ , n₂ ) <= n_u <= n₁ + n₂ 
so n_i <= n_u 
So apart from the time taken to iterate through every element of the two linklists which will be same for both cases time taken for union will be more or equal to intersection.
Hence A should be the answer. Isn't it?

---

For Union:

First copy the values of L1 to a new linked list L3. This takes n1 iterations.
Now for each element of L1, check whether it is present in the L2. (Let L2 contain n2 items). If yes, don't copy them and if No then copy them to L3. Then total number of iterations needed is n1*n2.

Net TC: T(n1)+T(n1*n2)=T(n1*n2)

For intersction:

For each element of L1, check whether it is present in the L2. (Let L2 contain n2 items). If yes, then copy them to new L3, if No then don't copy them (Just the opposite of the previous one). Ultimately total number of iterations needed here is also n1*n2.

In case of union you may be required to make more nodes but that comes under the time considered for each iteration. So creation of nodes inside an iteration won't add up to the time complexity as it is a constant time taking operation.

---

Suppose list 1 is of size m and list 2 is of size n.

Sort both of them using merge sort and this will take $O(mlogm+nlogn)$ time.

Now, union and intersection of both lists can be done in $O(m+n)$ time.

So, if lists are unordered, then it would take $O(mlogm+nlogn)$ 

References:

https://www.geeksforgeeks.org/merge-sort-for-linked-list/

https://www.geeksforgeeks.org/intersection-of-two-sorted-linked-lists/

---

Union intersection will take O.nlogn time using merge sort

---

when we for the merge operation for the 2 sorted lists then during each merge operation while comparing if we find 2 values to be the same we will basically choose only one value.right?

---

Its not correct to write n1+n2 for operations like membership and cardinality since they are performed on a single set . there is no such thing as membership of set 1 in set 2... ( thats subset not membership)

---

what is meant by cardinality here, suppose S1={1,2,3} and S2={2,3,4}. so we want the cardinality of S1 and S2 individually or S1US2(for this we will first need the union to be performed)

I’m a bit confused...

---

cardinality is unary operation so only one set (i.e LL ) is given as input you have to find no of elements in LL

---

Here is a linear time (average case) algorithm for intersection by using hash table

1: Insert all elements of S1 in hash table H – O(n)

2: Let S3 = new linked list

3: Traverse through all elements of S2. If an element is present in H, insert it in S3. – O(n)

Worst case is $O(n^2)$ but average case is O(n). So can the answer be option A?

---

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.