What is the time complexity of ordered operations in TreeSet?

Actually, I'd have thought that those operations are all going to be O(logN) for a general implementation.

• For first() and last() to be O(1) the TreeSet implementation would need to maintain a pointer to the leftmost and rightmost leaf nodes in the tree respectively. Maintaining these adds a constant cost to every insertion and at least a constant cost to every deletion. In reality, the implementation will probably find the left / rightmost nodes on the fly ... which is an O(logN) operation.

• The lower() and higher() methods have to do the same work as get and are therefore O(logN).

Of course, you can check the source-code yourself to see what actually happens. (As other people have done: see below.)

Looks like both first() and last() will be O(log n) and not O(1)based on Implentation(sun jdk 1.6.0_23) of TreeMap which is used by TreeSet by default:

 /**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

/**
 * Returns the last Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

I actually looked up the source code, in http://developer.classpath.org/doc/java/util/TreeSet-source.html, first() calls maps.firstKey() then in http://developer.classpath.org/doc/java/util/TreeMap-source.html

393: public K firstKey()
394: (
395: if (root == nil)
396: throw new NoSuchElementException();
397: return firstNode().key;
398: )

and in firstNode(), it does the while loop to go all the way to the left

952: final Node<K, V> firstNode()
953: (
954: // Exploit fact that nil.left == nil.
955: Node node = root;
956: while (node.left != nil)
957: node = node.left;
958: return node;
959: )