What is the runtime complexity in Big O of the Java TreeMap firstEntry() method?

Question

I know that this class uses a Red-Black tree but does that mean that it is O(log(n)) to get the least element or is it O(1) or something else?

Thanks!

Answer 1

Given it is a binary search tree, it must traverse the height of the tree (which is O(log n)) in order to reach the first (i.e. least) entry, so indeed the method is O(log n).

You can see how it is implemented in OpenJDK here.

/**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

---

If you're looking for a structure supporting constant-time find-minimum, maybe look into using a binary min heap, where the root node corresponds to the minimum. Note this is a totally different data structure with different semantics.