3
$\begingroup$

I am confused whether space complexity of a recursive algorithm depends on the total number of recursive calls or not.

Say I have an algorithm which has exponential function calls, but stack size is linear, so in that case we can say that space complexity is not proportional to number of recursive calls but if we say that does it depend on the total number of recursive calls or not, then does it make sense to make such a statement because after all stack is made because of the recursive calls only?

So is it better to say that "stack size depends on the recursive calls but not on the total number of recursive calls"? Is this statement valid?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes, that's right.

The statement "space complexity is $f(n)$" means that, if we had only $f(n)$ memory and no more, it would still be possible to run the algorithm.

As an example, say we are generating all permutations of length $n$ recursively. Then we make $c_1 \cdot n!$ recursive calls but, at every moment, use at most $c_2 \cdot n$ memory. A hypothetical machine with $c_2 \cdot n$ memory, and no more, would still run the algorithm correctly.

The space complexity depends on the structure of recursive calls, not simply on their number.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.