Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Python

Calculating Fibonacci Numbers

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

We'll cover the following...

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 Python function that returns the nthn^{th} Fibonacci number.

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

Python 3.5
def fib(num):
  """
  Finds nth fibonacci number
  :param num: An integer number
  :return: nth fibonacci number
  """
  if num <= 1:
    return num
  return fib(num - 1) + fib(num - 2)
# Driver code to test above function
if __name__ == '__main__':
  num = 6
  print(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) represents 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 7 and the two subtractions and one addition on line 9. Lastly, T(1)=1T(1) = 1 and T(0)=1T(0) = 1 represents the base-cases.

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

eq 1: T(n)=2T(n−1)+4T(n) = 2T(n-1)+4

Also by this relation,

eq 2: T(n−1)=2T(n−2)+cT(n-1) = 2T(n-2)+c, where c=4c = 4

So, we can replace T(n−1)T(n-1) in eq 1 with the value of it in eq 2 like so to get,

T(n)=2(2T(n−2)+c)+cT(n) = 2(2T(n-2)+c)+c

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

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

=8T(n−3)+7c= 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)=2kT(n−k)+(2k−1)c T(n) = 2^kT(n-k)+(2^k-1)c \space

where kk 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            k=1T(n) = 2T(n-1)+c \;\;\;\;\;\; \color{red} k \color{red}= \color{red}1

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

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

⋯\cdots

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

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

=2n−1+c2n−1−c= 2^{n-1}+ c2^{n-1}-c

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

Hence,

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

This means that the fib(n) function is in O(2n)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 make this better? Well, it turns out that these redundant calculations can be eliminated, which would reduce the time complexity of the algorithm significantly using a technique called memoization.