GATE CS 2004 Q40 — Linked Lists

Let the two sets $A$ and $B$ be represented as linked lists of sizes $m$ and $n$ respectively, with elements in arbitrary (unsorted) order.

Let's analyze the worst-case time complexity for each operation:

1. Membership: To check if an element $x$ belongs to a set of size $n$, we perform a linear search through the linked list.
   Time Complexity: $O(n)$
2. Cardinality: To find the number of elements in a set of size $n$, we traverse the entire list to count the nodes.
   Time Complexity: $O(n)$
3. Intersection: To find $A \cap B$, we must check each of the $m$ elements of list $A$ against all $n$ elements of list $B$ to find common elements.
   Time Complexity: $O(m \cdot n)$
4. Union: To find $A \cup B$ without duplicates, we can copy all elements of $A$ to the result list. Then, for each of the $n$ elements of $B$, we must search the list $A$ (or the result list) to ensure it is not a duplicate before adding it.
   Time Complexity: $O(m \cdot n)$

Comparing these, union and intersection require quadratic time $O(n^2)$ (assuming $m \approx n$), making them significantly slower than membership and cardinality, which only require linear time $O(n)$.

Therefore, the slowest operations are union and intersection.