Clever Geek Handbook

TreeMap lookup time lastKey

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

The oracle docs mentions TreeMaps:

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

+3


source to share


2 answers


According to the implementation in Open JDK this 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;
}


lastKey()

a call getLastEntry()

that continues to accept the correct subtree until additional nodes are accepted. Since the implementation keeps the tree in a balanced state, the number of iterations is O (log N).

+4


source


If TreeMap

can guarantee O (log (n)) for containsKey()

(as it is), then it should be able to do lastKey()

in O (log (n)). Any tree structure that can be sure to yield an O (log (n)) key lookup can also support a O (log (n)) max key lookup.



While nothing inherently precludes the realization of a brain dead center that is getting worse, I think it's pretty safe to give up this opportunity for java.util.TreeMap

.

+2


source






More articles:


All Articles