# Finding Fibonacci – Exponential vs. Linear

## 2ndFriday Fun Session – 13th Jan 2017

### What is Fibonacci number?

0, 1, 2, 3, 5, 8 . . . is Fibonacci series where 1st number is 0, 2nd number 1, 3rd number 2 and so on, each number being the sum of its two predecessors.

### What are we talking about here?

We will see that nth Fibonacci number can be found using both recursive and iterative methods. Recursive one will be prohibitively expensive while iterative one will be much more efficient.

### Recursive solution

We can use the following recursive function to get nth Fibonacci number.

```int FibonacciExponential(int n, int &opCounter)
{
opCounter++;

if(n == 0 || n == 1)
return n;

return FibonacciExponential(n-1, opCounter) +
FibonacciExponential(n-2, opCounter);
}```

We have passed an extra parameter to count the number of times the recursive function gets called. For example, for n = 4, we see we have the following calls, each node showing the value of n, with which the function is called. Many a times, for a certain value of n, the function is called numerous times.

We see, if we increase n by one, the tree also expands by one more level. For n = 4 we end up with 24 (2 raised to the 4th power) calls. It will be few less as the right sub-tree is one level less than the left, but they are negligible. When the input number n (input size) goes as an exponent, we call the complexity – exponential. Especially, when we talk about Big O notation, we express it using the upper asymptotic bound. The complexity here is O(2n).

The value 2n when n = 100, is 2100 = 1267650600228229401496703205376. What if each operation takes a millisecond? The execution time would be trillions of years ~ just for n = 100!

### Iterative solution

We could as well run a simple loop by retaining the previous two values and add them to find the present Fibonacci number. For n = 100, we just needed to loop maximum 100 times, requiring 100 operations. That means, we could call the complexity linear and in terms of big O notation it would be O(n).

The below function finds nth Fibonacci number iteratively, in linear time.

```int FibonacciLinear(int n, int &opCounter)
{
opCounter++;

if(n == 0 || n == 1)
return n;

int result = 0;
int previousPrevious = 0;
int immediatePrevious = 1;

for(int i=2; i<=n; i++)
{
opCounter++;

result = immediatePrevious + previousPrevious;

previousPrevious = immediatePrevious;
immediatePrevious = result;
}

return result;;
}```

Considering each operation taking 1 millisecond, we are talking about 100 milliseconds for linear algorithm vs. trillions of years for exponential algorithm.

GitHub: Fibonacci Code

Index

## Author: Gopal Das

Data Scientist @ CrimsonLogic, Singapore BS in CSE from Khulna University ME in Internet Science & Engineering from Indian Institute of Science (IISc) Publications on Query Optimization in RDBMS in ACM SIGMOD, IEEE ICDE etc. Founding team member and VP Engineering of iTwin, a spinoff from A*STAR Software engineer/data scientist for 19 years Software, Database, ML Father of 3 (two @ NUS High and one is too little!) www.linkedin.com/in/dasgopal https://github.com/gopalcdas