Computational Complexity of TreeSet methods in Java

Question

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?

Solution

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)

Comments

[user1628340]

@PeterSmith - are they all O(ln n) in terms of node search time? (n= number of nodes)?

[Vishy]

Correct. As comparisons can be much more expensive than skipping from one node to another this can more useful to consider. e.g. a first/last() on a TreeSet with 2 billion elements (the largest) can be faster than one comparison e.g. in a Set with one element.

[xudifsd]

@PeterLawrey How about the time complexity of removing element from iterator of TreeSet? Still O(ln n) or O(1)?

[Ahmed Gamal]

I think not all are o(logn) the implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

[Vishy]

@AhmedGamal Thank you for the correction. As a percentage, most methods are not O(ln N), the operations which work on one element are.

[Kevin Sheng]

Why are add(), remove(), etc. O(ln n) instead of the usual O(log_2 n)? Is there some special optimization that allows it to be executed base e instead of base 2?

[Vishy]

@KevinSheng Scale doesn't matter so O(ln N) and O(log2 N) are the same, the first is simpler.