What is the time complexity of ordered operations in TreeSet?

java algorithm complexity-theory treeset
signalseeker picture signalseeker · Mar 7, 2011 · Viewed 7.5k times · Source

What is the time complexity of the following operations in java.util.TreeSet?

  • first()
  • last()
  • lower()
  • higher()

I would assume that these are constant time but the API makes no guarantees.

Answer

Stephen C picture Stephen C · Mar 7, 2011

Actually, I'd have thought that those operations are all going to be O(logN) for a general implementation.

  • For first() and last() to be O(1) the TreeSet implementation would need to maintain a pointer to the leftmost and rightmost leaf nodes in the tree respectively. Maintaining these adds a constant cost to every insertion and at least a constant cost to every deletion. In reality, the implementation will probably find the left / rightmost nodes on the fly ... which is an O(logN) operation.

  • The lower() and higher() methods have to do the same work as get and are therefore O(logN).

Of course, you can check the source-code yourself to see what actually happens. (As other people have done: see below.)

Related questions

Example of O(n!)?

What is an example (in code) of a O(n!) function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More