title: Code complexity Explanation | Powerset Generation
body: <p>I am trying to understand difference/similarity in complexities when writing the code to generate powerset in 2 ways:</p>
  <pre><code>def powerset(s, i, cur):
      if i==len(s):
          print(cur)
          return 
      
      powerset(s, i+1, cur+s[i]) # string addition is also possibly O(n^2) here?
      powerset(s, i+1, cur)
  
  powerset(&quot;abc&quot;, 0, &quot;&quot;)
  </code></pre>
  <p>Output:</p>
  <pre><code>['abc', 'ab', 'ac', 'a', 'bc', 'b', 'c', '']
  </code></pre>
  <p>This is going into recursion, with 2 choices at each step (adding <code>s[i]</code> or not), creating 2 branches. Leading to <code>2^n</code> and adding to the array/printing is another <code>O(n)</code>, leading to <code>O(n*2^n)</code>
  Also thinking about it in the terms of <code>branches^depth</code> = <code>O(2^n)</code></p>
  <p>The space complexity for this will be: <code>O(n)</code>? Considering max depth of the tree to go up to <code>n</code> by the above logic.</p>
  <p>And with this:</p>
  <pre><code>s = &quot;abc&quot;
  res = [&quot;&quot;]
  
  for i in s:
      res += [j+i for j in res]
  </code></pre>
  <p>I get the same output.
  But here, I see 2 for loops and the additional complexity for creating the strings -- which is possibly <code>O(n^2)</code> in Python. Leading to possible <code>O(N^4)</code> as opposed to <code>O(n*2^n)</code> in the solution above.
  Space complexity here seems to me to be <code>O(n)</code> since we are reserving space for just the output. But no additional space, so overall: <code>O(1)</code></p>
  <p>Is my understanding for these solutions in time and space correct? I was under the impression that computing powerset is <code>O(2^n)</code>. But I figured maybe its a more optimized solution? (even though the second solution seems more <em>naive</em>).</p>
  <br>
  https://stackoverflow.com/questions/34008010/is-the-time-complexity-of-iterative-string-append-actually-on2-or-on
  <br>
  Here, they suggest using arrays to avoid the `O(n^2)` complexity of string concatenation.