16.4 generating power set space complexity

#1

Hi guys,

the book states that the space complexity of the recursive solution is O(2^n) even if we just want to print the subsets. In my opinion it is O(n), since the stack has maximum length of n and all function arguments are re-used across recursive calls.

Could you explain please?

1 Like
#2

Hey @damluar,

Thanks for the report, and we have revised this to O(n) space complexity assuming you just wanna printing the result without holding it.

0 Likes