The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 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 (69k points) | 2k views
if linked list are sorted then union, intersection both takes O(m+n) bcoz of merge algo.
What is meant by membership?
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 )

3 Answers

+38 votes
Best answer

answer - (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 Boss (9.3k 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.
+14 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 Veteran (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.


–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 Veteran (14.3k 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.


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

33,593 questions
40,128 answers
38,389 users