title: What is the running time of this powerset algorithm
body: <p>I have an algorithm to compute the powerset of a set using all of the bits between 0 and 2^n:</p>
  
  <pre><code>public static &lt;T&gt; void findPowerSetsBitwise(Set&lt;T&gt; set, Set&lt;Set&lt;T&gt;&gt; results){
          T[] arr = (T[]) set.toArray();
          int length = arr.length;
  
          for(int i = 0; i &lt; 1&lt;&lt;length; i++){
              int k = i;
              Set&lt;T&gt; newSubset = new HashSet&lt;T&gt;();
              int index = arr.length - 1;
              while(k &gt; 0){
                  if((k &amp; 1) == 1){
                      newSubset.add(arr[index]);
                  }
                  k&gt;&gt;=1;
                  index --;
              }
              results.add(newSubset);
          }
  
      }
  </code></pre>
  
  <p>My question is: What is the running time of this algorithm. The loop is running 2^n times and in each iteration the while loop runs lg(i) times. So I think the running time is</p>
  
  <p><code>T(n) = the sum from i=0 to i=2^n of lg(i)</code></p>
  
  <p>But I don't know how to simplify this further, I  know this can be solved in O(2^n) time (not space) recursively, so I'm wondering if the method above is better or worse than this, timewise as it's better in space.</p>