Assume ordered sets that support O(n) iteration and O(log n) access to single items, what is theoretically optimal complexity for set-union, set-intersection and set-difference? Assume that a dedicated structure could be used for the sets, as long as the result is of the same type as the input.
Edit:
Let n be the size of the larger set, m the size of the smaller set and d the size of the symmetric difference.
An algorithm is described in this paper. It runs in O(m*log(n/m)) which is claimed to be optimal. The algorithm is then modified in this paper so that it also becomes O(d*log(n/d)).
Is it a contradiction that an optimal algorithm can be improved? I guess not since d is a new parameter, O(m*log(n/m)) is still optimal with respect to n and m. But is this the end or how fast is possible?