Suppose each set is represented as a linked list with elements in arbitrary…
2004
Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?
- A.
union only
- B.
intersection, membership
- C.
membership, cardinality
- D.
union, intersection
Attempted by 305 students.
Show answer & explanation
Correct answer: D
Answer: union and intersection are the slowest.
Explanation: Let m and n be the sizes of the two sets represented as unsorted linked lists.
Membership: search for a single element in an unsorted linked list — O(n) time.
Cardinality: counting all elements if the size is not stored — O(n) time.
Intersection: for each element of one list, check membership in the other list — O(m * n) time in the worst case (quadratic).
Union: add all elements of the first list (O(m)), then for each element of the second list check membership in the result to avoid duplicates — worst-case O(m * n) time (quadratic).
Therefore, union and intersection are the slowest operations because they involve repeated membership checks across the lists, yielding quadratic time; membership and cardinality are only linear.
A video solution is available for this question — log in and enroll to watch it.