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?

Christology

Either way, a simple look at the source of TreeMap would show they are O(1) operations. The documentation even hints this, stating the submap uses the original map. – Galway

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.

Breaker

Getting them is O(1), iterating them would need more. The iterator calls successor() N times, where N is the number of elements between range. I would say O(N). – Invalidity

Answer 2

I was able to browse the source of TreeMap to get the detailed implementation.

If you go in detail with the source code as to how they are actually getting the subMap its something like this...

If you see the size method of NavigableSubMap

  public int size() {
        return (fromStart && toEnd) ? m.size() : entrySet().size();
    }

The entrySet() implementation in multiple calls final calls up getCeilingEntry() function

final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}

SO i guess to get the actual map from the created submap; the time complexity is more than O(1).

Christology

Where do the methods subMap, headMap, tailMap make a call to NavigableSubMap.size()? – Breaker

Yup they don't but they do call getceilingentry() in subsequent calls like the size() method. I just used size() as an example. – Christology

All three methods make only invokcations to constructors leading to NavigableSubMap. Where do they make invocations to GetCeilingEntry()? See line 826 which leads to line 1677, which then finally leads to line 1235. – Breaker

Okay let me explain this way. When you do this treesetobj.subMap(args) it creates a navigableSubMap object (say navobj). But when you do navobj.keySet() then it calls the getCeilingEntry() function. So its like it doesnt make the actual submap when calling the constructor. Only when operations like keySet() and size() are called it actually tries to fetch the submap. – Christology