Временная сложность операций TreeMap - subMap, headMap, tailMap

Кто-нибудь знает временную сложность операций TreeMap вроде - subMap, headMap. tailMap.

Временная сложность операций типа get, put равна O (logn). Но Javadoc мало говорит о сложности вышеуказанных операций.

Наихудший вариант сложности, который я могу представить, - это O (n), поскольку он будет проходить через весь список, если набор включает в себя последний элемент. Можем ли мы это подтвердить?