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

Question

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

Do TreeMap

and TreeSet

keep track of the number of items they contain, or should they count them every time you call size()

? The Javadoks remain mute on this issue.

+3

java data-structures

Jason s 15 Mar 12 at 21:20

source to share

2 answers

Yes, they keep track of how many objects they contain, so the call size()

either gives O (1) runtime.

+1

CodeBlind 15 Mar 12 at 21:24

source to share

yshavit · Accepted Answer · 2012-03-15T21:21:43+0000

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

Later, the Java source treemap was used to search Google. (I'm not saying it was snarky - it's not entirely obvious that the source code will be there for googlin ').

tl; dr version is what they track, so O (1).

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

More articles: