Fibonacci Numbers

Definition

f(n) = \begin{cases} 0, & \mbox{if } n\mbox{ = 0} \\ 1, & \mbox{if } n\mbox{ = 1 } \\ F(n-1) + F(n-2), & \mbox{if } n\mbox{ \textgreater 1 } \end{cases}

Fibonacci numbers grow rapidly.

f(n) = 2^{\frac{n}{2}} \hspace{1cm} for \hspace{1cm} n \geq 6

Proof By Induction

Base Case:
n = 6,7 (by direct computation)

Inductive step:
f(n) = f(n-1)+f(n-2)\\ \geq 2^{\frac{n-1}{2}} + 2^{\frac{n-2}{2}} \\ \geq 2*2^{\frac{n-2}{2}} \\ \geq 2^{\frac{n}{2}}

Formula For nth Fibonacci Number

f(n) = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}  -\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right]

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:
f(n) = \begin{cases} 2, & \mbox{if } n \leq 1 \\ T(n-1) + T(n-2) + 3, & \mbox{else }  \end{cases}

From above T(n) >= Fn
T(100) \approx 1.77*10^21

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

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

T(n) = 2n + 2

E.g. T(100)= 202

Leave a Reply