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?

  1. A.

    union only

  2. B.

    intersection, membership

  3. C.

    membership, cardinality

  4. 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.

Explore the full course: Gate Guidance By Sanchit Sir