Search code examples
javaalgorithmtreeset

What is the time complexity of the tailSet operation of java.util.TreeSet?

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

Solution

  • AFAIK Taking the tailSet is O(log n), but iterating over the the last m elements is O(m * log n)