Time complexity of TreeMap<> operations: get() and subMap()

Question

Based on this post, Time complexity of TreeMap operations- subMap, headMap, tailMap

subMap() itself is O(1), and O(n) comes from iterating the sub map.

So, why use get(key) then?

We can use subMap(key, true, key, true) instead,

which is O(1) and iterating this sub map is also O(1).

Faster than get(key), which is O(log(n)). Something wrong here...

Manuelmanuela

Answer 1

We can use subMap(key, true, key, true) instead, which is O(1)

This is correct

and iterating this sub map is also O(1).

O(n) comes from the question. The answer says nothing to imply this, which is good, because it's not true.

Time complexity of iterating a subtree is O(log n + k), where n is the number of elements in the whole map, and k is the number of elements in the sub-map. In other words, it still takes O(log n) to get to the first position when you start iterating. Look up getFirstEntry() implementation to see how it is done.

This brings the overall complexity of your approach to O(log n), but it is bound to be slower than a simple get, because an intermediate object is created and discarded in the process.

Swineherd

Thanks man. Totally make sense to me. Thank you for taking time on my question. – Manuelmanuela

awesome answer. top 0.01% is not a joke. – Thalweg

Answer 2

The answer is a bit confusing. Technically it's true that creating the submap is constant operation. But that's just because it actually does nothing apart from setting the low and high keys and still shares the tree structure with the original tree.

As a result any operation on the tree is actually postponed until the specific method is invoked. So then get() still goes through the whole original map and only checks whether it didn't cross the low and high boundaries. Simply saying the get() is still O(n) where the n comes from the original map, not from the submap.

Tetra

Answer 3

The construction of subMap takes O(1) time, however all retrieval operations take the same O(log n) time as in the original map because SubMap just wraps this object and eventually complete a range check and delegate the invocation of get() method to the original source map object.

Portentous