Calculating Fibonacci Numbers

Classic recursive implementation of the Fibonacci series

Before we dive into what dynamic programming is, let’s have a look at a classic programming problem: the Fibonacci series. You’ve probably already seen it, but let’s start with a quick refresher. The Fibonacci series is a series of numbers in which each number is the sum of the preceding two numbers. The first two numbers are 0 and 1. So, it looks like 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Here is a C# method that returns the $n^{th}$ Fibonacci number.

This is the Fibonacci golden spiral. The width of each square represents a Fibonacci number.

Time complexity with recurrence relations

To calculate the time complexity of the code, we can solve a recurrence relation,

$$\begin{cases} T(0) = 0, \\ T(1) = 1, \\ T(n) = T(n-1)+T(n-2)+4 \end{cases}$$

$T(n)$ represents the Fib method. $T(n-1)$ and $T(n-2)$ represent the recursive calls to Fib(n-1) Fib(n-2), whereas the $4$ represents the basic operations in the code. Namely, the comparison on line 12 and the two subtractions and one addition on line 17. Lastly, $T(1) = 1$ and $T(0) = 1$ represent the base cases.

To solve this recurrence, we can simplify it by approximating that $T(n-1) \approx T(n-2)$. The time that is taken to calculate $T(n-1)$ is greater than the time taken to calculate $T(n-2)$, so this approximation gives us an upper bound on the total time complexity,

Eq 1: $T(n) = 2T(n-1)+4$.

Also, by this relation,

Eq 2: $T(n-1) = 2T(n-2)+c$, where $c = 4$.

So, we can replace $T(n-1)$ in eq 1 with its value in eq 2 like so to get,

$T(n) = 2(2T(n-2)+c)+c$

$= 4T(n-2)+3c$

$= 4(2T(n-3)+c)+3c$

$= 8T(n-3)+7c$

$\cdots$

You must have noticed a pattern here, which is that this equation can be written in generic terms.

Generic: $T(n) = 2^kT(n-k)+(2^k-1)c \space$

Here, $k$ is the number of times that the equation was substituted into plus one. Have a look at the following for a clearer picture:

$T(n) = 2T(n-1)+c \;\;\;\;\;\; \color{red} k \color{red}= \color{red}1$

$T(n) = 4T(n-2)+3c \;\;\;\; \color{red} k \color{red}= \color{red}2$

$T(n) = 8T(n-3)+7c \;\;\;\; \color{red} k \color{red}= \color{red}3$

$\cdots$

Let’s consider what value of $k$ brings the argument of $T(n-k)$ to the base case of 1. If $n - k = 1$, then $k = n - 1$. Next, we substitute $k = n - 1$ in the expression for $T(n)$. We can now put the generic equation in terms of $T(1)$, the value of which we know is $1$:

$T(n) = 2^{n-1}+(2^{n-1}-1)c$

$= 2^{n-1}+ c2^{n-1}-c$

$= 2^{n-1}(1+ c)-c \space$

Hence,

$$T(n) = 2^{n-1}(1+ c)-c$$

This means that the Fib(n) method is in $O(2^n)$, i.e., exponential time, which isn’t very efficient. What is causing this inefficiency and how can we improve this? Let’s take a look at that now.

Redundant calculations in classic Fibonacci

One factor is the fact that some terms of Fib(n) are calculated several times. Look at the following slides to see which ones are repeated in the case of Fib(6):

How can we improve this? Well, it turns out that these redundant calculations can be eliminated, which would significantly reduce the algorithm’s time complexity using a technique called memoization.