What is the Time Complexity of size() for Sets in Java? -

i know, seems stupid question, expect time complexity of size() on collection o(1) - i'm finding "optimization" in code requires call size() slowing things down.

so, time complexity of size() sets in java?

my code implementation of recursive algorithm find maximal cliques in graph (not important). basically, optimization checks whether 2 sets have equal size (these sets being constructed either way), , allows 1 more recursive call (stopping recursion after that) if equal in size.

here (simplified) version of code:

        private static void recursivelyfindmaximalcliques(set<integer> subgraph, set<integer> candidates, set<integer> notcandidates) {     boolean nofurthercliques = false;      iterator<integer> candidateiterator = candidates.iterator();     while (candidateiterator.hasnext()) {         int nextcandidate = candidateiterator.next();         candidateiterator.remove();         subgraph.add(nextcandidate);          set<integer> neighbors = getneighbors(nextcandidate);         set<integer> newcandidates = calculateintersection(candidates, neighbors);         set<integer> newnotcandidates = calculateintersection(notcandidates, neighbors);          //if (newcandidates.size() == candidates.size())         //  nofurthercliques = true;         recursivelyfindmaximalcliques(subgraph, newcandidates, newnotcandidates);         //if (nofurthercliques)         //  return;          subgraph.set.remove(nextcandidate);         notcandidates.set.add(nextcandidate);     } } 

the lines have commented out ones in question - can see check if sets newcandidates , candidates same size, , if are, recursion allowed go 1 level deeper.

when lines uncommented, code runs 10% slower - true whether sets used hashsets, treesets, or linkedhashsets. makes no sense, since lines ensure there fewer recursive calls.

the thing can assume call size() on sets taking long time. calling size() on sets in java take longer o(1)?

edit

since people have asked, here calculateintersection():

private static integerset calculateintersection(set<integer> seta, set<integer> setb) {     if (seta.size() == 0 || setb.size() == 0)         return new set<integer>();      set<integer> intersection = new set<integer>(); //replace treeset, hashset, or linkedhashset, whichever being used     intersection.addall(seta);     intersection.retainall(setb);     return intersection; } 

second edit here full code, if like. hesitated post it, since it's long , nasty, people asked, here is:

public class cliquefindingalgorithm {  private static class integerset {     public set<integer> set = new treeset<integer>();  //or whatever set being used }   private static arraylist<integerset> findmaximalcliques(undirectedgraph graph) {     arraylist<integerset> cliques = new arraylist<integerset>();     integerset subgraph = new integerset();     integerset candidates = new integerset();     integerset notcandidates = new integerset();      (int vertex = 0; vertex < graph.getnumvertices(); vertex++) {         candidates.set.add(vertex);     }      recursivelyfindmaximalcliques(cliques, graph, subgraph, candidates, notcandidates);     return cliques; }   private static void recursivelyfindmaximalcliques(arraylist<integerset> cliques, undirectedgraph graph,          integerset subgraph, integerset candidates, integerset notcandidates) {     boolean nofurthercliques = false;      iterator<integer> candidateiterator = candidates.set.iterator();     while (candidateiterator.hasnext()) {         int nextcandidate = candidateiterator.next();         candidateiterator.remove();         subgraph.set.add(nextcandidate);          integerset neighbors = new integerset();         neighbors.set = graph.getneighbors(nextcandidate);         integerset newcandidates = calculateintersection(candidates, neighbors);         integerset newnotcandidates = calculateintersection(notcandidates, neighbors);          if (newcandidates.set.size() == candidates.set.size())             nofurthercliques = true;         recursivelyfindmaximalcliques(cliques, graph, subgraph, newcandidates, newnotcandidates);         if (nofurthercliques)             return;          subgraph.set.remove(nextcandidate);         notcandidates.set.add(nextcandidate);     }      if (notcandidates.set.isempty()) {         integerset clique = new integerset();         clique.set.addall(subgraph.set);         cliques.add(clique);     } }   private static integerset calculateintersection(integerset seta, integerset setb) {     if (seta.set.size() == 0 || setb.set.size() == 0)         return new integerset();      integerset intersection = new integerset();     intersection.set.addall(seta.set);     intersection.set.retainall(setb.set);     return intersection; } 

}

public class undirectedgraph {  // ------------------------------ private variables ------------------------------  private arraylist<treemap<integer, double>> neighborlists; private int numedges;   // ------------------------------ constants ------------------------------    // ------------------------------ constructors ------------------------------  public undirectedgraph(int numvertices) {     this.neighborlists = new arraylist<treemap<integer, double>>(numvertices);     this.numedges = 0;     (int = 0; < numvertices; i++) {         this.neighborlists.add(new treemap<integer, double>());     } }   // ------------------------------ public methods ------------------------------   public void addedge(int vertexa, int vertexb, double edgeweight) {     treemap<integer, double> vertexaneighbors = this.neighborlists.get(vertexa);     treemap<integer, double> vertexbneighbors = this.neighborlists.get(vertexb);      vertexaneighbors.put(vertexb, edgeweight);     vertexbneighbors.put(vertexa, edgeweight);     this.numedges++; }   public list<integer> computecommonneighbors(int vertexa, int vertexb) {     list<integer> commonneighbors = new arraylist<integer>();     iterator<integer> iteratora = this.getneighbors(vertexa).iterator();     iterator<integer> iteratorb = this.getneighbors(vertexb).iterator();      if (iteratora.hasnext() && iteratorb.hasnext()) {         int nextneighbora = iteratora.next();         int nextneighborb = iteratorb.next();         while(true) {              if (nextneighbora == nextneighborb) {                 commonneighbors.add(nextneighbora);                 if (iteratora.hasnext() && iteratorb.hasnext()) {                     nextneighbora = iteratora.next();                     nextneighborb = iteratorb.next();                 }                 else                     break;             }              else if (nextneighbora < nextneighborb) {                 if (iteratora.hasnext())                     nextneighbora = iteratora.next();                 else                     break;             }              else if (nextneighborb < nextneighbora) {                 if (iteratorb.hasnext())                     nextneighborb = iteratorb.next();                 else                     break;             }         }     }      return commonneighbors; }  // ------------------------------ private methods ------------------------------  private class edgeiterator implements iterator<int[]> {      private int vertex;     private int[] nextpair;     private iterator<integer> neighboriterator;      public edgeiterator() {         this.vertex = 0;         this.neighboriterator = neighborlists.get(0).keyset().iterator();         this.getnextpair();     }      public boolean hasnext() {         return this.nextpair != null;     }      public int[] next() {         if (this.nextpair == null)             throw new nosuchelementexception();         int[] temp = this.nextpair;         this.getnextpair();         return temp;     }      public void remove() {         throw new unsupportedoperationexception();     }      private void getnextpair() {         this.nextpair = null;          while (this.nextpair == null && this.neighboriterator != null) {             while (this.neighboriterator.hasnext()) {                 int neighbor = this.neighboriterator.next();                  if (this.vertex <= neighbor) {                     this.nextpair = new int[] {vertex, neighbor};                     return;                 }             }              this.vertex++;             if (this.vertex < getnumvertices())                 this.neighboriterator = neighborlists.get(this.vertex).keyset().iterator();             else                 this.neighboriterator = null;         }        } }  // ------------------------------ getters & setters ------------------------------  public int getnumedges() {     return this.numedges; }   public int getnumvertices() {     return this.neighborlists.size(); }   public double getedgeweight(int vertexa, int vertexb) {     return this.neighborlists.get(vertexa).get(vertexb); }   public set<integer> getneighbors(int vertex) {     return collections.unmodifiableset(this.neighborlists.get(vertex).keyset()); }   public iterator<int[]> getedgeiterator() {     return new edgeiterator(); } 

}

it depends on implementation; example hashset.size() calls size() on internal hashmap returns variable;

//hashset public int size() {     return map.size(); }  //hashmap public int size() {     return size; }