Search code examples
javadictionarytreemapsortedmap

TreeMap lastKey lookup time

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.

Solution

  • 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).