Java\'s built-in TreeSet class uses time in O(log n) for insertion and deletion.

Question

Java's built-in TreeSet class uses time in O(log n) for insertion and deletion. It seems that we could build a O(n log n) sorting algorithm by simply inserting all of the data into a TreeSet (Figure 1), then traversing the TreeSet inorder. The running-time analysis is correct, but this algorithm fails to sort some ArrayLists. Why? (Hint: Think about the definition of a set.)

Figure 1

1 /** Sort data

2 public static <E extends Comparables<E>> void

3     sort(java.util.ArrayList<E> data) {

4     java.util.TreeSet<E> tree = new java.util.TreeSet<E>(data);

5     data.clear();

6     for (E item : tree) {

7         data.add(item);

8        }

9     }

Explanation / Answer

For any set data structure any time complexity will be expressed in terms of average

i.e. the time complexity to insert an element into tree set = O(log n ) average

but for some inputs it may take O(n) time in worst case and O(1) in best case

hence for those inputs which causes worst case time while adding, will causes the time complexity to be O(n2)

For example if it is using BST

then array which is already sorted will take O(n2) time to insert all the elements and O(n) for inorder traversal

total it will take O(n2) time

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.