Time complexity analysis using big-o

Question

After revising, we concluded that the time complexity is actually O(2^n)

The question is what is the time complexity? Is it O(2^n) or?

The reason I believe this is because of the for loop is considered to be runned n time. Then the nested while loop is runs 2^n time. The second while loop runs 2^n time.

Algorithm subsetsGenerator(T)     
Input:  A set T of n elements       
Output: All the subsets of T stored in a queue Q   {     

create an empty queue Q;      
create an empty stack S;     
let a1, a2, …,  an be all the elements in T;       
S.push({});    // Push the empty subset into the stack      
S.push({a1})         
for ( each element ai in T-{a1} )         
{ 
  while (S is not empty )                 
  {  
x=S.pop;                     
Q.enqueue(x);                        
x=x ∪ { ai };                     
Q.enqueue(x);                     
  }            

 if  ( ai is not the last element )                 
  while (Q is not empty )                     
  {  
  x=Q.dequeue();                         
  S.push(x);                         
  }          
 }    
} 

Edit: If you want me to break down the analysis, comment bellow.

Answer 1

For your set T of n elements, the total number of subsets is 2^n. If you want to keep all those subsets in Q, the time complexity is at least O(2^n).

---

Actually I think O(2^n) is the answer.

If I understand your algorithm correctly, you are trying to do for each element a_i in T, take out everything in S, put it back into S twice - once without a_i and once with a_i.

Hence the total time complexity is (1+2+4+...+2^n) times C, C stands for the time to pop, enqueue, dequeue, and push, which is O(1). The term above equals 2^(n+1)-1 which is still O(2^n).