Space Complexity of Recursion

Solution

Add two things: the memory the calls allocate explicitly, and the call stack. Each call holds a frame on the stack until it returns, so the stack part is the maximum number of frames on the stack at any one time, which is the maximum depth of the recursion. If each frame holds a fixed number of variables, the stack part is proportional to that depth.

Exercise

Here is a recursive method that returns the product of the elements of arr from index i to the end.

public static int product(int[] arr, int i) {
  if (i == arr.length) {
    return 1;
  }
  return arr[i] * product(arr, i + 1);
}

With $n$ the length of arr, give the time complexity and the auxiliary space of product(arr, 0), and justify the space.

Solution

Time is $O (n)$ : one call per element plus one base-case call, each doing constant work. Auxiliary space is $O (n)$ : each call recurses before it multiplies, so the call for index 0 is still on the stack when the call for index 1 is made, and so on down to the base case. At that moment all $n + 1$ frames are on the stack at once, so the maximum depth is $n + 1$ .

Solution

public static int product(int[] arr) {
  int result = 1;
  for (int i = 0; i < arr.length; i++) {
    result = result * arr[i];
  }
  return result;
}

Time is unchanged at $O (n)$ . Auxiliary space changed from $O (n)$ to $O (1)$ : one accumulator and one index, and no stack of pending calls.

Exercise

Here is the direct recursive Fibonacci, with $n$ the value of the argument.

public static int fib(int n) {
  if (n <= 1) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

Give its time complexity and its auxiliary space. Then explain why the two are in different complexity classes.

Solution

Time is $O (2^{n})$ : each call with $n \geq 2$ makes two more calls, so the number of calls roughly doubles at each of about $n$ levels, and every call does constant work. Auxiliary space is $O (n)$ : the deepest the stack ever gets is one chain fib(n), fib(n - 1), …, fib(1), about $n$ frames.

Time counts every call the method ever makes. Space counts only the largest number of calls that are on the stack at the same time.

Solution

public static int fib(int n) {
  if (n <= 1) {
    return n;
  }
  int prev = 0;
  int curr = 1;
  for (int i = 2; i <= n; i++) {
    int next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

One loop from 2 to n doing constant work per pass is $O (n)$ time. A fixed number of int variables, whatever $n$ is, is $O (1)$ auxiliary space.

Exercise

Here are two binary searches over a sorted int[], one iterative and one recursive. Both return the index of target or -1. The recursive one is started with search(arr, target, 0, arr.length - 1).

public static int search(int[] arr, int target) {
  int lo = 0;
  int hi = arr.length - 1;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) {
      return mid;
    } else if (arr[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

public static int search(int[] arr, int target, int lo, int hi) {
  if (lo > hi) {
    return -1;
  }
  int mid = (lo + hi) / 2;
  if (arr[mid] == target) {
    return mid;
  } else if (arr[mid] < target) {
    return search(arr, target, mid + 1, hi);
  } else {
    return search(arr, target, lo, mid - 1);
  }
}

For each version give the best-case time, the worst-case time, and the auxiliary space. What differs between them, and what does not?

Solution

Binary search	Best-case time	Worst-case time	Auxiliary space
Iterative	$O (1)$	$O (lo g n)$	$O (1)$
Recursive	$O (1)$	$O (lo g n)$	$O (lo g n)$

In the best case target is the middle element and the first comparison finds it. In the worst case target is not in the array and the range is halved about $lo g n$ times. The time is the same for both versions. The auxiliary space is not. The loop reuses lo, hi, and mid. The recursion makes one call per halving, and those frames stay on the stack until the base case, so the stack reaches depth $lo g n$ .