Code complexity Explanation | Powerset Generation

Question

I am trying to understand difference/similarity in complexities when writing the code to generate powerset in 2 ways:

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("abc", 0, "")

Output:

['abc', 'ab', 'ac', 'a', 'bc', 'b', 'c', '']

This is going into recursion, with 2 choices at each step (adding s[i] or not), creating 2 branches. Leading to 2^n and adding to the array/printing is another O(n), leading to O(n*2^n) Also thinking about it in the terms of branches^depth = O(2^n)

The space complexity for this will be: O(n)? Considering max depth of the tree to go up to n by the above logic.

And with this:

s = "abc"
res = [""]

for i in s:
    res += [j+i for j in res]

I get the same output. But here, I see 2 for loops and the additional complexity for creating the strings -- which is possibly O(n^2) in Python. Leading to possible O(N^4) as opposed to O(n*2^n) in the solution above. Space complexity here seems to me to be O(n) since we are reserving space for just the output. But no additional space, so overall: O(1)

Is my understanding for these solutions in time and space correct? I was under the impression that computing powerset is O(2^n). But I figured maybe its a more optimized solution? (even though the second solution seems more naive).

https://stackoverflow.com/questions/34008010/is-the-time-complexity-of-iterative-string-append-actually-on2-or-on
Here, they suggest using arrays to avoid the `O(n^2)` complexity of string concatenation.

The size of a powerset is 2^n. It is impossible to compute it with time or space complexity under 2^n, because you have to, at a minimum, store each value. — Zorgoth, May 22 '22 at 18:59
Yeah, I was under the same impression, but this second solution tripped me. I'm a little confused on that. — user2816215, May 22 '22 at 18:59
res will eventually be size ~2^n, so looping through res is more expensive than O(n). — Zorgoth, May 22 '22 at 19:00

rici · Answer 1 · 2022-05-23T07:47:17.593

It's clear that both of those solutions involving creating 2^len(s) strings, which are all the subsets of s. The amount of time that takes is O(2^len(s) * T) where T is the time to create and process each string. The processing time is impossible to know without seeing the code which consumes the subsets; if the processing consisting only of printing, then it's presumably O(len(s)) since printing has to be done character by character.

I think the core of your question is how much time constructing the string takes.

It's often said that constructing a string by repeated concatenation is O(n²), since the entire string needs to be copied in order to perform each concatenation. And that's basically true (although Python has some tricks up its sleeve which can optimise in certain cases). But that's assuming that you're constructing the string from scratch, tossing away the intermediate results as soon as they're no longer necessary.

In this case, however, the intermediate results are also part of the desired result. And you only copy the prefixes implicitly, when you append the next character. That means that the additional cost of producing each subset is O(n), not O(n²), because the cost of producing the immediate prefix was already accounted for. That's true in both of the solutions you provide.

Code complexity Explanation | Powerset Generation

1 Answers1