java - What is the space complexity of enumerating subsets? -

this based off other question had on space complexity. permutation space complexity

this solution problem of enumerating(naming) sets. (tested it, works)

public static void subsets(set<integer> s) {     queue<integer> copytoprotectdata  = new linkedlist<integer>();     for(int member: s) {         copytoprotectdata.add(member);     }     generatesubsets(copytoprotectdata, new hashset<integer>()); } private static void generatesubsets(queue<integer> s,           set<integer> hashset) {     if(s.isempty()) {         system.out.println(hashset);     } else {         int member = s.remove();         set<integer> copy = new hashset<integer>();         for(int i:hashset) {             copy.add(i);         }         hashset.add(member);         queue<integer> queuecopy = new linkedlist<integer>();         for(int i:s){             queuecopy.add(i);         }         generatesubsets(s, hashset);         generatesubsets(queuecopy, copy);                } } 

i know time complexity of algorithm of o(2ⁿ) because solution in discrete math set n has 2ⁿ subsets. acceptable way of evaluating time complexity of algorithm(couldn't find recurrence relation this)?

moving on though, still having difficulties of evaluating space complexity. trying apply learned last question. in last question on permutations of string, @ajb said because of fact store local string grows 1 on each recursive call, space complexity o(n²).

trying apply same here. lets test set {1,2,3}. generate subset {1,2,3}, algorithm, when {1,2,3} printed, these "subsets" exist in memory, - {1}, {}, {1,2},{1],{1,2,3}, {1,2}, meaning not subset has 1 less element in permutations problem. made copies of leftovers @ each round 1 operation in 1 side won't affect copy on other side. why wasn't sure if @ajb's strategy work here. runtime still o(n²) or greater?

typically way you'd go analyzing complexity if want bound through mix of amortized analysis , other methods - example, can try rewrite recursion in iterative form easier analysis.

to answer questions more directly: runtime not o(2^n).

these parts of code going increase complexity o(n*2^n)

    for(int i:hashset) {         copy.add(i);     }      for(int i:s){         queuecopy.add(i);     } 

the reason being going iterate on not every subset, every element of every subset.

with regards space complexity question, , assuming garbage collection on top of things, yes space complexity o(n^2). though making copies of 2 things instead of 1, complexity still o(n^2) because affects constant factor. if want save list of subsets, puts space complexity way o(n*2^n) - you'll still need output anyway.