What is the time complexity of the tailSet operation of java.util.TreeSet?
algorithm, java, treeset
Solution
AFAIK Taking the tailSet is O(log n), but iterating over the the last `m` elements is `O(m * log n)`
Problem
I was implementing the 2D closest pair algorithm using sweepline, and it says that you need to find the six points above a certain y coordinate. What I did is I put the points in a TreeSet sorted by y-coordinate, and used the tailSet method to get all points above a certain point, and iterate up to 6 times. I was wondering if the complexity of the tailSet operation is O(log n), and if it is, is iterating over the tailSet at most six times also O(log n)? Reference: http://people.scs.carleton.ca/~michiel/lecturenotes/ALGGEOM/sweepclosestpair.pdf