What is the time complexity of the lowerKey()
operation in Java implementation of TreeMap
?
I think it is log(n) but I can't find it anywhere in the documentation.
The complexity of more basic operation is well documented:
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
BTW: I'm also interested in the complexity of subMap()
. I guess that a log(n) complexity of lowerKey()
will allow log(n) time for constant size subMap()
.
lowerKey()
is a search in a balanced binary search tree, so it's obviouslyO(log n)
. You might want to read the source code, e.g. from here, to see how the tree is traversed.Similarly, each operation with a
NavigableMap
returned fromsubMap()
also requiresO(log n)
because you will need to traverse the tree to find elements you want.