My understanding ofTreeSet's first() method is that it will take O(log n) based of the explanation in this answer.

The explanation in that answer says that for it to be o(1) we would need to maintain a pointer to the first element in the TreeSet which would add a constant time to every operation. However, doesn't Java already maintain such a pointer since the iterator() method of a collection must be O(1)? i.e couldn't we just instantiate the iterator in O(1) and get the first element using next() in constant time?

CodePudding user response：

iterator() returns an object that implements the Iterator interface. This can be accomplished in constant time, of course.

E. g. the iterator might manage a pointer to the current element. At the beginning this pointer might be null, so that the first call of hasNext() would have to walk down the tree to the first element, which should have a complexity of O(log n).