Alguien sabe la complejidad temporal de las operaciones de TreeMap como - subMap, headMap. mapa de cola

La complejidad de tiempo de las operaciones como get, put es O (logn). Pero el javadoc no dice mucho sobre la complejidad de las operaciones anteriores.

En el peor de los casos, puedo pensar en O (n), ya que pasará por toda la lista si el conjunto incluye el último elemento. ¿Podemos confirmarlo?