1

Good day! I saw a backtracking subset-generation algorithm in the link:

https://www.geeksforgeeks.org/backtracking-to-find-all-subsets/

which claims that the space complexity of the program is O(n). Yet, from what I've learned, the minimum complexity should be O(2^n) since it will be the size of our output. Is the given space complexity correct?

Schadenfreude
  • 11
  • 1
  • 1
  • 1
    This isn't really a question on Stack Overflow... did you try to ask in the comments to the article? – Felix Jun 03 '21 at 04:32
  • @Felix I just needed to clear it up as soon as possible. I apologize for asking in the wrong place. – Schadenfreude Jun 03 '21 at 04:47
  • 1
    The article mentions that time complexity is O(2^n) and space complexity is O(n). If you store output in something like an array, the space complexity would also be O(2^n). But you could also feed the output to some other algorithm one subset at a time. For example, you can check if a boolean formula is satiable without storing 2^n possible solutions. – hilberts_drinking_problem Jun 03 '21 at 04:53
  • Does this answer your question? [Is the space complexity of this subset algorithm actually O(n)?](https://stackoverflow.com/questions/29225659/is-the-space-complexity-of-this-subset-algorithm-actually-on) – Yilmaz Feb 04 '22 at 08:01

0 Answers0