Space complexity of a recursive algorithm from the CTCI book

Question

I am going through the CTCI book and can't understand one of their examples. They start with:

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

and explain that it's O(n) time and O(n) space because each of the calls is added to the call stack and takes up actual memory.

The next example is:

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

and states that time complexity is O(2^n) and space is O(n). Although I understand why the time is O(2^n), I am not sure why the space is O(n)? Their explanation is that "only O(n) nodes exists at any given time". Why we don't count the space taken by each call stack, as it is in the first example?

P.S. After reading similar questions, should I assume that stack frame's space is reclaimed once we start moving back (or up) the recursion?

score 0 · Accepted Answer · answered May 01 '20 at 08:24

Unlike the time complexity, which is simply a total time that is needed to run a program, the space complexity describes the space required to execute the program. So it doesn't really matter that there are 2ⁿ nodes in the execution tree of the program. The call stack automatically folds and releases the additional memory used. What matters is the maximal depth of the call tree, which is O(n) for this program. Should be noted, though, that recursion is a special case that naturally releases any used memory upon stack fold. If memory is allocated explicitly during runtime, it should be released explicitly as well.

Regarding the first example, the call tree is simply a list of depth n, resulting in similar complexity of O(n).

Space complexity of a recursive algorithm from the CTCI book

1 Answers1