The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usually destroyed by the operation. Show how to support UNION in O(1) time using a suitable list data structure.
UNION of two lists
2
$\begingroup$
algorithms
-
3First, your question belongs to http://programmers.stackexchange.com . Second, it obviously depends on how do you implement a set and on what operations performance do you measure (e.g. what if c3 = UNION(c1, c2) executes in O(1), but any operation on c3 executes on O(n!)?( – 2012-07-03
-
0Well, of course it depends and I believe we should choose a suitable list data structure for solving the problem. For example, for a singly linked list I can't find any solution and it's impossible in my humble opinion. I'll try to ask on programmers.stackexchange.com if there is wrong place for my question, sorry. – 2012-07-03
-
2@penartur: programmers.SE is definitely not the place -- that site is for question about programming as a job/social/business activity rather than about particular technical questions. The question might be relevant at the CS site (but in my opinion that doesn't prevent the topic from being welcome here, too). – 2012-07-03
-
0Henning Makholm - Thank you. I will be glad to discuss it anywhere. – 2012-07-03