1

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?

GhostCat
  • 137,827
  • 25
  • 176
  • 248
Hisham Hijjawi
  • 1,803
  • 2
  • 17
  • 27
  • 1
    Who said `next()` was constant time? – Dan Getz Aug 01 '22 at 18:43
  • 1
    And who says that `iterator()` needs to be `O(1)`? https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations tells you that `next()` is `O(n)` btw. – GhostCat Aug 01 '22 at 18:45
  • @GhostCat [This answer](https://stackoverflow.com/questions/40371854/the-time-complexity-of-iterator-in-java) led me to believe that iterator() should be O(1). – Hisham Hijjawi Aug 01 '22 at 19:00

1 Answers1

1

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).

Mihe
  • 2,270
  • 2
  • 4
  • 14