Home/

...

/

Untitled Masterpiece

In this lesson, we'll look at the classic method to find the nth Fibonacci number and its time complexity using recurrence relations.

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 have 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 Java function that returns nth the Fibonacci number.

Here is the Fibonacci Golden Spiral. The width of each square represents a Fibonacci number.
Press + to interact
Java
class Fibonacci {
 //Finds nth fibonacci number
 public static int fib(int i) {
  if (i <= 1)
   return i;
  return fib(i - 1) + fib(i - 2);
 }
 //driver code to test the function
 public static void main(String args[]) {
  System.out.println(fib(6));
 }
};

Time complexity with recurrence relations

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

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

T(n)T(n) represents the fib function. T(n−1)T(n-1) and T(n−2)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 4 and the two subtractions and one addition on line 6. Lastly, T(1)=1T(1) = 1 and T(0)=1T(0) = 1 represent the base-cases.

To solve this recurrence, we can simplify it by approximating that T(n−1 ...