Linked list operation time

Please help me out with the following question,I am unable to actually make out the right option,I am able to make out only the correct option as intersection ,and that too not sure with it so what should be the approach followed for solving this question.

gate

Replies

  • Ankita Katdare
    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.
  • radha gogia
    radha gogia
    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.

You are reading an archived discussion.

Related Posts

A study done by IBM researchers in India in collaboration with a hardware R&D firm called RadioStudio have found that discarded laptop-batteries can still power slums in India and other...
As mechanical engineers & graduates set out to learn the CAD software, they are often confused as to which software to choose. The popular ones being, CAD, Solidworks and Pro/Engineer,...
Following some of the big Chinese manufacturers in electronics like Lenovo, Xiaomi, Oppo, Gionee, and Huawei, another Chinese handset maker Vivo is expected to enter Indian market soon. Vivo, a...
Spinnakr is a Privately held Information Technology and Services company founded by Michael Mayernick and Adam Bonnifield in the year 2011. Spinnakr is based out of Washington DC, United States....
As humans, we are naturally gifted to identify patterns when we are shown only a handful of examples. On the contrary, computer systems require huge data sets to be able...