On the complexity of a set-union problem

We consider a simple data structure supporting the following operations: (i) create a new singleton set; (ii) create a new set which is the union of two pre-existing sets; (iii) determine whether a given element is in a particular set. We prove both lower and upper bounds for an implementation of such a data structure. In a restricted model we show that no deterministic implementation can be better than the “trivial” one that takes O(n²) time. In a parallel model where the operations come in at most O(1g n) stages we exhibit a sub-quadratic implementation