18,939 views
62 votes
62 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}$

4 Answers

Best answer
101 votes
101 votes

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

edited by
50 votes
50 votes
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.
0 votes
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

–2 votes
–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
Answer:

Related questions

55 votes
55 votes
8 answers
1
103 votes
103 votes
11 answers
2
27 votes
27 votes
3 answers
4
Kathleen asked Sep 18, 2014
8,748 views
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?preorder and postorderi...