Running time of set union operation

Question

Given two sets A and B, what is the common algorithm used to find their union, and what is it's running time?

My intuition:

a = set((1, 2, 3))
b = set((2, 3, 5))
union = set()
for el in a:
    union.add(el)

for el in b:
    union.add(el)

Add checks for a collision, which is O(1), and then adds the element, which is (??). This is done n times (where n is |a| + |b|). So this is O(n * x) where x is avg running time for the add operation.

Is this correct?

Answer 1

The complexity of add/find(collision), would depend on the implementation of union.

If you are using some hashtable based datastructure then your collision operation will indeed be constant assuming a good hash function.

Otherwise, add will probably be O(Log(N)) for a sorted list/tree datastructure.