title: why powerset gives 2^N time complexity?
body: <p>The following is a recursive function for generating powerset </p>
  
  <pre><code>void powerset(int[] items, int s, Stack&lt;Integer&gt; res) {
       System.out.println(res);
  
       for(int i = s; i &lt; items.length; i++) {
            res.push(items[i]);
            powerset(items, s+1, res);
            res.pop();
       }
  }
  </code></pre>
  
  <p>I don't really understand why this would take <code>O(2^N)</code>. Where's that <code>2</code> coming from ?
  Why <code>T(N) = T(N-1) + T(N-2) + T(N-3) + .... + T(1) + T(0)</code> solves to <code>O(2^n)</code>. Can someone explains why ?</p>