Difference in performance of adding elements in Treeset directly vs transferring from arraylist?

Question

I want to know the difference in performance between adding element in a TreeSet one by one versus adding elements in ArrayList and then transferring to TreesSet by .addAll() method. I know TreeSet uses Red–black tree as its data structure. Just want to know the basic internal workings of this two process. Which one of the following will be faster and why?

    TreeSet<Integer> ts = new TreeSet<Integer>();   
    for(int i=0;i<n;i++)
        ts.add(sc.nextInt());

OR,

   TreeSet<Integer> ts = new TreeSet<Integer>();    
   ArrayList<Integer> ar = new ArrayList<Integer>();
        for(int i=0;i<n;i++)
            ts.add(sc.nextInt());

            ts.addAll(ar);

Here sc is an object of Scanner class(it may be anything else as well). Any help will be deeply appreciated. Thanks in advance.

Answer 1

TreeSet.addAll(c) method does the optimization only if the c is an instance of SortedSet. In other cases it just iterates over the collection and adds elements one by one.

Therefore, it does not make any sense to put elements into ArrayList first and then use TreeSet.addAll(list) method. You will get worse performance and higher memory consumption.

From the big-O perspective, both solutions have n*log(n) complexity.

EDIT. TreeSet has 2 important properties: Elements are unique and they are sorted. If you are only interested in the unique-elements property, using a HashSet would give you a complexity of n.

Answer 2

Only in case the Collection being passed to addAll(Collection) is instanceof SortedSet and instanceof TreeMap the tree creation time is linear.

In your second case creating an ArrayList takes extra time. Rest being same since TreeSet#addAll internally calls Collection#add() in for loop

So, its better to call add then addAll if the Collection already is not available