The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+32 votes

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?

  1. $\text{union}$ only

  2. $\text{intersection, membership}$

  3. $\text{membership, cardinality}$

  4. $\text{union, intersection}$

asked in DS by Veteran (52.1k points) | 3.6k views
if linked list are sorted then union, intersection both takes O(m+n) bcoz of merge algo.
Union isn't simply merging ! we need to eliminate duplicates also while taking union. So for each element in list1, we need to traverse the entire list2 once which takes O(n*m) time.

Similar is the case for intersection.
why dont you sort firsr befor union and intersection it will make it O(nlogn + mlogm )
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 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

4 Answers

+49 votes
Best answer

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)$

answered by Loyal (8.7k points)
edited by
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 n1 as no. of input in one linklist and n2 as no. of input in second linklist.
if ni is no. of nodes need to be created for intersection and nu is no. of nodes nedd to be created for union
0 <= ni <= min(n1 , n2 )
max(n1 , n2 ) <= nu <= n1 + n
so ni <= n
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)$ 


+26 votes

 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.
answered by Boss (23.4k points)
very well explained
very clear soln. Thanx
but using merge sort we can find union and intersection in $O(nlgn)$ time
yeah reena O(nlogn + mlogm)

@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
0 votes

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

answered by Active (4.1k points)
–2 votes
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
answered by Boss (14.4k points)
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 have to check it in the other list for finding out duplicates.(by binary search) 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 is not efficient.linear search is better than binary search in linked list.


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,811 questions
54,540 answers
75,603 users