Time and Space of Recursive Fibonacci

Let’s look at another recursive method. The Fibonacci numbers are defined by $F (0) = 0$ , $F (1) = 1$ , and $F (n) = F (n - 1) + F (n - 2)$ for $n \geq 2$ . The definition is recursive, so the most direct way to compute it is a recursive method:

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

Let $n$ be the value of the argument and work out the time and space complexity of this method.

Time Complexity of `fib`

Every call to fib with $n \geq 2$ makes two more calls, and each of those makes two more, and so on. Let’s lay out all the calls that fib(5) makes:

                                  fib(5)
                      ┌──────────────┴───────────────┐
                   fib(4)                         fib(3)
             ┌────────┴────────┐               ┌─────┴─────┐
          fib(3)            fib(2)          fib(2)      fib(1)
       ┌─────┴─────┐       ┌───┴───┐       ┌───┴───┐
    fib(2)      fib(1)  fib(1)  fib(0)  fib(1)  fib(0)
   ┌───┴───┐
fib(1)  fib(0)

There are two things to notice here.

The first is how the tree grows. Almost every call splits into two more, so each level down has roughly twice as many calls as the level above it. The tree is about $n$ levels deep, because the leftmost chain of calls goes fib(n), fib(n-1), fib(n-2), down to the base case. Doubling $n$ times gives about $2^{n}$ calls in total. Each call by itself does a constant amount of work, one comparison and one addition, so the total work is proportional to the number of calls. The running time is exponential, $O(2^n)$.

The second thing is how much of that work is repeated. Look at the tree again: fib(3) is computed twice, and fib(2) is computed three times. For larger $n$ there is even more repetition. The recursion does not remember what it has already computed, so it computes the same subproblems again every time it reaches them. This repeated work is what makes the running time exponential.

How accurate is the

O (2^{n})

bound?

The bound $O (2^{n})$ is a little loose. I counted as if every call split into two calls of the same size, but they are not the same size. fib(n - 2) has a smaller subtree than fib(n - 1), so the tree is not quite full. The call count actually grows like $φ^{n}$ , where $φ = \frac{1 + 5}{2} \approx 1.618$ is the golden ratio. That is smaller than $2^{n}$ , but it is still exponential, and $O (2^{n})$ is still a correct upper bound.

Space Complexity of `fib`

The method is recursive, so let’s see how deep the stack gets.

It is tempting to say $2^{n}$ , since that is how many calls there are. But the stack holds only the calls that have not returned yet, and most of those $2^{n}$ calls have already returned. Java evaluates fib(n - 1) completely, all the way down and back up, before it even starts fib(n - 2). So most calls have already returned rather than piling up on the stack. The deepest the stack ever gets is one chain down the left side, fib(n) → fib(n - 1) → … → fib(1):

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ fib(1)  n=1  return 1  (base case) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌────────────────────────────────────┐
        │ fib(2)  n=2  waiting for fib(1)    │
        ├────────────────────────────────────┤
        │ fib(3)  n=3  waiting for fib(2)    │
        ├────────────────────────────────────┤
        │ fib(4)  n=4  waiting for fib(3)    │
        ├────────────────────────────────────┤
        │ fib(5)  n=5  waiting for fib(4)    │
        └────────────────────────────────────┘

That is about $n$ frames, so the auxiliary space complexity is $O(n)$. The input is a single number, so the input space is $O (1)$ , and the total space complexity is $O (n)$ .

Time and Space of Recursive Fibonacci

Time Complexity of fib

Space Complexity of fib

Time Complexity of `fib`

Space Complexity of `fib`