## 2^{nd} Friday Fun Session – 13^{th} Jan 2017

### What is Fibonacci number?

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

### What are we talking about here?

We will see that n^{th} 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 n^{th} 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 2^{4} (2 raised to the 4^{th} 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(2 ^{n})*.

The value 2^{n} when n = 100, is 2^{100} = 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 n^{th} 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