A Faster Fibonacci

Let’s stay with Fibonacci. In this and next sections, we are going to improve the algorithm, and we will watch what each improvement does to its time and space complexity.

The recursive fib does an exponential amount of work, and most of it is wasted. It keeps recomputing subproblems we have already solved. Computing fib(5) recomputes fib(3) twice and fib(2) three times. The repetition only gets worse as $n$ grows.

It works this way because fib(n) asks for fib(n - 1) and fib(n - 2), and those ask for still smaller values, all the way down to the base cases. When a value is finally computed, it is not stored anywhere, so the other calls that need the same value cannot use it.

What if we computed each Fibonacci number exactly once and kept it, so that when we need it again we look it up instead of recomputing it?

Let’s work from the bottom up. Start with the two values we already know, $F(0)=0$ and $F(1)=1$. Then compute $F(2)$ from them, $F(3)$ from $F(1)$ and $F(2)$, and keep going up. Each new number is the sum of the two before it. Store them in an array as we go, so every value we need is already there by the time we need it:

public static int fib(int n) {
  if (n <= 1) {
    return n;
  }
  int[] f = new int[n + 1];
  f[0] = 0;
  f[1] = 1;
  for (int i = 2; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  return f[n];
}

To compute fib(5), we set the first two cells and then the loop fills the array left to right, one cell per pass:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│░0░│░1░│ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┘
      ↑
    i = 1

Each pass writes f[i] = f[i - 1] + f[i - 2], using the two cells immediately to its left (shaded). Here is fib(2) computed from fib(1) and fib(0):

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│░0░│░1░│ 1 │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┘
          ↑
        i = 2

Then fib(3) is computed from fib(2) and fib(1):

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│░0░│░1░│░1░│ 2 │ _ │ _ │
└───┴───┴───┴───┴───┴───┘
              ↑
            i = 3

Then fib(4) is computed from fib(3) and fib(2):

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│░0░│░1░│░1░│░2░│ 3 │ _ │
└───┴───┴───┴───┴───┴───┘
                  ↑
                i = 4

Then fib(5) is computed from fib(4) and fib(3):

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│░0░│░1░│░1░│░2░│░3░│ 5 │
└───┴───┴───┴───┴───┴───┘
                      ↑
                    i = 5

Each pass reads two cells, and both of them were filled in on earlier passes, so nothing is computed twice.

Let $n$ be the value of the argument. What is the time complexity of this version? What is its space complexity?

Time. There is a single loop running from 2 to n, doing a constant amount of work each pass (two array reads, one addition, and one array write). That is about $n$ steps, so the running time is $O(n)$. The recursive version was $O(2^n)$.

Space. The method allocates an array of $n+1$ integers, so its auxiliary space is $O(n)$. (As before, the input is a single number, so the input space is $O(1)$.)

To compute one number, fib now builds and holds an array of $n+1$ integers. The recursive version holds only its stack frames.