educative.io

Educative

How space complexity is O(N*2^N) instead of O(N)?

hi I could understand the space complexity comes from the result and the queue we use to keep track of intermediate results.
for the result, the space complexity is O(2^N).
for the queue, it’s O(2^(N-1)).
sum them up, the space complexity is O(2^N). where does the ‘N*’ come from?
really appreciate your help. thanks!

It comes from the fact that each element in the results (and in the queue) has a length of O(n).

1 Like