What is the time complexity of floorEntry() method of NavigableMap?

Question

If I have a NavigableMap already formed. What will be the time required for a floorEntry() operation to execute? will it be O(1) or O(logn)?

for example:

If I have a NavigableMap with n intervals, and I use map.floorEntry(k) for some random k, what will be the time complexity of the execution of the operation?

Answer 1

NavigableMap is an interface, so I can't answer for any implementation of that interface. However, for the TreeMap implementation, floorEntry() requires log(n) time.

The Javadoc of TreeMap only states that

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

but the implementation of floorEntry() is similar to the implementation of get() in terms of complexity.

Both call a helper method (get() calls getEntry() and floorEntry() calls getFloorEntry()) that performs most of the logic, and both of the helper methods have a while loop that advances to the left or right child in each iteration, until it finds what it is looking for or reaches a leaf. Thus the required time is the depth of the tree - O(log(n)).

Here are the implementations of getEntry() and floorEntry():

/**
 * Returns this map's entry for the given key, or {@code null} if the map
 * does not contain an entry for the key.
 *
 * @return this map's entry for the given key, or {@code null} if the map
 *         does not contain an entry for the key
 * @throws ClassCastException if the specified key cannot be compared
 *         with the keys currently in the map
 * @throws NullPointerException if the specified key is null
 *         and this map uses natural ordering, or its comparator
 *         does not permit null keys
 */
final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

/**
 * Gets the entry corresponding to the specified key; if no such entry
 * exists, returns the entry for the greatest key less than the specified
 * key; if no such entry exists, returns {@code null}.
 */
final Entry<K,V> getFloorEntry(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 (cmp < 0) {
            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;
            }
        } else
            return p;

    }
    return null;
}