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?

Answer: D. union, intersectionAnswer: 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…

  1. A.

    union only

  2. B.

    intersection, membership

  3. C.

    membership, cardinality

  4. D.

    union, intersection

Attempted by 408 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: Iocl Engineers Officers Grade A Paper 2

Loading lesson…