Linked list operation time

So, this is the question:

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

I think the answer should be D.

For intersection n*n comparisons are required.
For union n*n comparisons are required. (As after merging of two lists, we again have to find out the common elements)
A combination of both above will be the slowest.
Also, For Membership & Cardinality both - only n comparisons are needed.

Let's however wait for more answers.

Ankita Katdare

So, this is the question:

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

I think the answer should be D.

For intersection n*n comparisons are required.
For union n*n comparisons are required. (As after merging of two lists, we again have to find out the common elements)
A combination of both above will be the slowest.
Also, For Membership & Cardinality both - only n comparisons are needed.

Let's however wait for more answers.

Mam,please can you explain why cardinality would take n comparisons when in each set we will have to check for duplicate elements also,since cardinality is number of distinct elements,therefore,it would too work like union operation checking for duplicate elements,so it must also take nearly the same time as union operation.