Time complexity of TreeMap operations- subMap, headMap, tailMap

Question

Does anyone know the time complexity of the operations of TreeMap like - subMap, headMap. tailMap.

The time complexity of operations like get, put is O(logn). But the javadoc doesnt say much about the complexity for the above operations.

The worst case complexity I can thinks of O(n) since it will go through the entire list if the set includes the last element. Can we confirm it?

Answer 1

For those questions having the source code on hand is very useful as with sufficient IDE support you can simply browse through the implementation. When looking at the source code of TreeMap it can be seen, that all three methods construct a new map by using the constructor of AscendingSubMap:

public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                K toKey,   boolean toInclusive) {
    return new AscendingSubMap(this,
                               false, fromKey, fromInclusive,
                               false, toKey,   toInclusive);
}

Which does nothing else then to pass the parameters up with the super constructor to the class NavigableSubMap:

super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);

So all three methods are based on the following constructor:

NavigableSubMap(TreeMap<K,V> m,
                boolean fromStart, K lo, boolean loInclusive,
                boolean toEnd,     K hi, boolean hiInclusive) {
    if (!fromStart && !toEnd) {
        if (m.compare(lo, hi) > 0)
            throw new IllegalArgumentException("fromKey > toKey");
    } else {
        if (!fromStart) // type check
            m.compare(lo, lo);
        if (!toEnd)
            m.compare(hi, hi);
    }

    this.m = m;
    this.fromStart = fromStart;
    this.lo = lo;
    this.loInclusive = loInclusive;
    this.toEnd = toEnd;
    this.hi = hi;
    this.hiInclusive = hiInclusive;
}

All I can see here are invocations to compare for type and assertion checking reasons. Hence, it should be pretty much O(1).

You can always browse the source code online, but I really recommend to get the source files and link them to your IDE of choice.