TreeMap lastKey lookup time

Question

What is the time complexity of TreeMap.lastKey() part of the SortedMap interface?

The oracle docs mention this about TreeMaps:

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

Answer 1

According to the implementation in the Open JDK, it is O(log N):

public K lastKey() {
    return key(getLastEntry());
}
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

The lastKey() calls getLastEntry(), which continues to take the right subtree until there are no further nodes to take. Since the implementation maintains the tree in a balanced state, the number of iterations is O(log N).

Answer 2

If TreeMap can guarantee O(log(n)) for containsKey() (as it does), then it should be able to do lastKey() in O(log(n)) as well. Any tree structure that can be certain to yield O(log(n)) key lookups can also support finding the maximum key in O(log(n)).

Although nothing inherently rules out a brain-dead implementation that does worse, I think it's pretty safe to discount that possibility for java.util.TreeMap.