Computational complexity of TreeSet operations in Java?

Question

I am trying to clarify some things related to the complexity of some TreeSet operations. The javadoc says:

"This implementation provides a guaranteed log (n) of time for basic operations (add, delete and contains)."

So far so good. My question is what happens with addAll (), removeAll (), etc. Here the javadoc for Set says:

"If the specified collection is also set, the addAll operation effectively modifies this set so that its value is the union of two sets."

Is it just an explanation of the logical result of the operation or a hint about complexity? I mean, if two sets are represented, for example, by red-black trees, it would be better to somehow join the trees than to "add" each element of one to the other.

In any case, is there a way to combine two TreeSets into one with O (logn) complexity?

Thanks in advance.: -)

Answer 1

You could imagine how special cases could be optimized to O(log n) , but the worst case should be O(m log n) , where m and n are the number of elements in each tree.

Edit:

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

Describes a special case algorithm that can join trees in O(log(m + n)) , but note the limitation: all members of S1 must be less than all members of S2 . This is what I had in mind that for special cases there are special optimizations.

Answer 2

Looking at the java source for the TreeSet, it looks like this, if the SortedSet object is passed to the collection, then it uses the O (n) time algorithm. Otherwise, it calls super.addAll, which I assume will result in O (n logn).

EDIT - I think I read the code too fast, TreeSet can only use the O (n) algorithm if it keeps the map empty

Answer 3

According to this blog post:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html

this is O (n log n). Since the documentation does not give any indication of complexity, you can write your own algorithm if performance is important to you.

Answer 4

It is not possible to merge trees or sets of joins, as in data structures with split sets, because you do not know if the elements in the two trees intersect. Since the data structures have knowledge of the contents in other trees, it is necessary to check whether one element exists in another tree before adding to it, or at least try to add it to another tree and stop adding it if you find the path. So it should be O (MlogN)