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...

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.