patternMinor
Does the space complexity of a recursive algorithm depend on the total no of recursive calls?
Viewed 0 times
totalcallsthespacealgorithmrecursivedoesdependcomplexity
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#93989, answer score: 3
Revisions (0)
No revisions yet.