Recursive Runtime - Space Complexity (pg.44 of Cracking the Coding Interview)

Question

On pg. 44 of Cracking the Coding Interview, there is the following algo:

int f(int n) {
    if (n <= 1) {
        return 1;
    }
    return f(n - 1) + f(n - 1);
}

The book says that this has time complexity of O(2^n) and space-complexity of O(n). I get the time complexity part since there are O(2^n) nodes created. I don't understand why the space-complexity is not also that. The book says because it's because only O(n) nodes exist at any given time.

How can that be? Wouldn't the call-stack have all 2^n calls when we are at the bottom level of f(1)? What am I missing?

Please let me know if I can provide more detail.

Thanks,

Answer 1

No. The second call to f(n-1) doesn't take place until after the first one returns, so they do not occupy stack space at the same time. When the first one returns, its stack space is freed and may be reused for the second call.

The same applies at every level of the recursion. The memory used is proportional to the maximum depth of the call tree, not the overall number of nodes.