Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java TreeMap time complexity - lowerKey

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

like image 462
zvisofer Avatar asked Sep 29 '25 09:09

zvisofer


1 Answers

lowerKey() is a search in a balanced binary search tree, so it's obviously O(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 from subMap() also requires O(log n) because you will need to traverse the tree to find elements you want.

like image 94
dejvuth Avatar answered Oct 02 '25 06:10

dejvuth



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!