Menu
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.
796
Likewise, the TreeSet has O(log(n)) time complexity for the operations listed in the previous group. This is because of the TreeMap implementation. The time complexity for ConcurrentSkipListSet is also O(log(n)) time, as it's based in skip list data structure.
Objects in a TreeSet are stored in a sorted and ascending order. TreeSet does not preserve the insertion order of elements but elements are sorted by keys.
The objects of the TreeSet class are stored in ascending order. The important points about the Java TreeSet class are: Java TreeSet class contains unique elements only like HashSet.
According to the API, TreeSet uses a TreeMap internally, which is based on a "Red-Black tree" algorithm.
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.)
83
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
