Search code examples
javaguavatime-complexityspace-complexity

TreeRangeMap time and space complexities

I'm looking to guava TreeRangeMap that seem to very well suit my needs for a project. The java docs says that is based on a (java standard ?) TreeMap that have O(log(n)) time for get, put and next.

But the TreeRangeMap should be some kind of range tree implementation that according to this SO question have O(k + log(n)) time complexity for queries, O(n) space, with k being the range size?. Can somebody confirm this?

I'm also very interested in the time complexity of TreeRangeMap.subRangeMap() operation. Does it have the same O(k + log(n))?

Thanks.

Solution

  • It's a view, not an actual mutation or anything. subRangeMap returns in O(1) time, and the RangeMap it returns has O(log n) additive cost for each of its query operations -- that is, all of its operations still take O(log n), just with a higher constant factor.

    Source: I'm "the guy who implemented it."