CODEWITHSUNDEEP
javaalgorithmtreeset
Alvin John Burgos
Alvin John Burgos

Reputation: 43

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

Upvotes: 4

Views: 5289

Answers (2)

acridity
acridity

Reputation: 31

Hmm... It’s strange to me. I thought that in terms of big O a process of creating a tailSet inside java.util.TreeSet is O(1).

Small clarification: tailSet(), headSet() and subSet() return very small objects that delegate all the hard work to methods of the underlying set. No new set is constructed. Hence O(1) and pretty insignificant.

a link for discussion

Upvotes: 3

Peter Lawrey
Peter Lawrey

Reputation: 533442

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

Upvotes: 5

Related Questions