BTreeMap nth() improvements

1

Suggestion: BTreeMap/BTreeSet O(log(n)) n-th element access reads like "we can't do O(log(n)) so that's that".

Maybe we can't improve the order of complexity but we can improve the constant factor.

At a minimum we know the size so we could iterate from the nearest end halving the time.

Could we also skip up to 2B of leaf nodes at a time rather than iterating through each one individually?

I'm curious what's the best we can do without converting BTree into an Order statistic tree - Wikipedia?

2 Likes
2

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.