title: Computational complexity of TreeSet operations in Java?
body: <p>I am trying to clear up some things regarding complexity in some of the operations of TreeSet. On the javadoc it says: </p>
  
  <blockquote>
    <p>"This implementation provides
    guaranteed log(n) time cost for the
    basic operations (add, remove and
    contains)."</p>
  </blockquote>
  
  <p>So far so good. My question is what happens on addAll(), removeAll() etc. Here the javadoc for Set says:</p>
  
  <blockquote>
    <p>"If the specified collection is also a
    set, the addAll operation effectively
    modifies this set so that its value is
    the union of the two sets."</p>
  </blockquote>
  
  <p>Is it just explaining the logical outcome of the operation or is it giving a hint about the complexity? I mean, if the two sets are represented by e.g. red-black trees it would be better to somehow join the trees than to "add" each element of one to the other.</p>
  
  <p>In any case, is there a way to combine two TreeSets into one with O(logn) complexity?</p>
  
  <p>Thank you in advance. :-)</p>