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

Calculating Fibonnacci Numbers

Explore the calculation of Fibonacci numbers through classic recursion, understand the exponential time complexity via recurrence relations, and learn how dynamic programming techniques such as memoization reduce redundant computations to optimize performance.

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

The Fibonacci Golden Spiral. The width of each square represents a Fibonacci number.
C++
#include <iostream>
using namespace std;
int fib(int i){
  if (i <= 1)
    return i;
  return fib(i - 1) + fib(i - 2);
}
int main(){
  int n = 6;
  cout << fib(n) << endl;
}

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 2 and the two subtractions and one addition on line 4. 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)≈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 means 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

We can now put the generic equation in terms of T(1)T(1) the value of which we know is 11. This can be done by setting n−kn-k equal to 11,   n−k=1⇒k=n−1\; n-k = 1 \Rightarrow k = n-1 which would mean, T(n)=2n−1T(1)+(2n−1−1)c T(n) = 2^{n-1}T(1)+(2^{n-1}-1)c \space

We can substitute the value of T(1)T(1) which is 11 into the equation to get,

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 can be causing this and how can we make this better?

Redundant Calculations

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),

Turns out that these redundant calculations can be eliminated which would reduce the time complexity of the algorithm significantly using a technique called memoization.