What is the time complexity of lower()/higher() of TreeSet in Java?

Question

I know the time complexity of basic operations such as add, get is O(logn). But I didn't found the detail of lower() and higher(). So, what is the time complexity of lower() and higher() of TreeSet in Java?

Answer 1

TreeSet is backed by an implementation of NavigableMap called TreeMap. The code ultimately called when computing lower() on TreeSet is lowerEntry() on TreeMap.

/**
 * Returns the entry for the greatest key less than the specified key; if
 * no such entry exists (i.e., the least key in the Tree is greater than
 * the specified key), returns {@code null}.
 */
final Entry<K,V> getLowerEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

Looking at this code, it looks like with each iteration of the while loop, every branch either returns or traverse one level of the tree. Since Tree Map should have log(n) levels, the entire method has O(log(n)) complexity.