Computational Complexity of TreeSet methods in Java

user1628340 picture user1628340 · Jan 17, 2013 · Viewed 11.2k times · Source

Is the computational complexity of TreeSet methods in Java, same as that of an AVLTree?

Specifically, I want to know the computational complexity of the following methods: 1.add 2.remove 3.first 4.last 5. floor 6. higher

Java Doc for method description: http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

For an AVL Tree, there are all O(logn)? Whats the complexity of the above TreeSet Methods?

Answer

Peter Lawrey picture Peter Lawrey · Jan 17, 2013

Operations which work on a single element are all O(ln n) comparisons except first and last which are O(1) comparisons or O(ln N) node search time.

comparator(), iterator(), clear(), first(), isEMpty(), size(), last(), pollFirst(), pollLast() are O(1)

add(), ceiling(), contains(), floor(), headSet(), higher(), lower(), remove(), subSet(), tailSet() are O(ln N)

clone(), equals(), hashCode(), toArray() and toString() are O(n)