CODEWITHSUNDEEP
javadata-structures
Jason S
Jason S

Reputation: 189876

Java collections: TreeMap.size() and TreeSet.size(): O(1) or O(n)?

Do TreeMap and TreeSet keep track of how many items they contain, or do they have to count them every time you call size()? The javadocs remain mute on the subject.

Upvotes: 3

Views: 270

Answers (2)

CodeBlind
CodeBlind

Reputation: 4567

Yes, they do keep track of how many objects they contain, so calling size() on either yields O(1) runtime.

Upvotes: 1

yshavit
yshavit

Reputation: 43456

Take a look:

http://www.docjar.com/html/api/java/util/TreeMap.java.html

http://www.docjar.com/html/api/java/util/TreeSet.java.html

For future reference, the google search was "java source code treemap". (I'm not saying that to be snarky -- it's not entirely obvious that the source code would be out there for the googlin').

tl;dr version is that they keep track, so it's O(1).

Upvotes: 8

Related Questions