**Definition**

Fibonacci numbers grow rapidly.

**Proof By Induction**

Base Case:

n = 6,7 (by direct computation)

Inductive step:

Formula For nth Fibonacci Number

**NaiveAlgorithm**

FibRecurs(n): if n<=1: return n; else: return FibRecurs(n-1) + FibRecurs(n-2)

**Python Implementation**

def fibonnaci(n): if n<=1: return n else: return fibonnaci(n-1)+fibonnaci(n-2) a = fibonnaci(50) print("f(100) : ", a)

Running Time:

From above T(n) >= Fn

T(100) takes around 56000 years to calculate on 1 GHz processor.

**Reason why this Algorithm is so slow**

Fn = Fn-1 + Fn-2

Fn-1 = Fn-2 + Fn-3

Fn-2 = Fn-3 + Fn-4

……….

As you can see, in this method we are calculating same function value again and again.

To avoid this, we can use arrays to store previously calculated values. Which leads to our new algorithm.

FibList(n): create an array F[0...n] F[0] <- 0 F[1] <- 1 for i from 2 to n: F[i] = F[i-1] + F[i-2] return F[n]

Python Implementation

Python Implementation

def fibonnaci(n): f = [] for n in range(0, n): if n <= 1: f[n] = n else: f[n] = f[n-1] + f[n-2] return f[n] a = fibonnaci(0) print("f(100) : ", a)

Runtime

Runtime

T(n) = 2n + 2

E.g. T(100)= 202