Skip to main content

Fibonacci Sequence Problem

1. Problem​

Given an integer nn, calculate the nthn^\text{th} term of the Fibonacci sequence FnF_n.

FnF_n is defined by:

  • F0=0F_0=0
  • F1=1F_1=1
  • ∀n>1,Fn=Fn−1+Fn−2\forall n>1,\quad F_{n}=F_{n-1}+F_{n-2}

2. Naive Solution​

def fibonacci(n:int):
    if n==0:
        return 0
    elif n==1:
        return 1
    return fibonacci(n-1)+fibonacci(n-2)

Let TnT_n be the cost of calculating nn using this algorithm

2.1 Lower Bound​

We have:

Tn=Tn−1+Tn−2+O(1)≥Tn−1+Tn−2T_n=T_{n-1}+T_{n-2}+\mathcal{O}(1)\ge T_{n-1}+T_{n-2}

With T0=T1=1T_0=T_1=1, and by recursion we can prove that:

∀n∈N,Tn≥Fn\forall n\in\mathbb{N},\quad T_n\ge F_n

But, (Tn)n∈N(T_n)_{n\in\mathbb{N}} is increasing, so:

Tn≥2Tn−2  ⟹  Tn≥2n2T0T_n\ge 2T_{n-2}\implies T_n\ge 2^{\frac{n}{2}}T_0

By that we have Tn=Ω(Fn)=Ω(2n2)T_n=\Omega(F_n)=\Omega(2^{\frac{n}{2}})

2.2 Upper Bound​

We also have for some fixed K>0K>0:

Tn≤Tn−1+Tn−2+KT_n\le T_{n-1}+T_{n-2} +K

We can prove by induction that:

Tn≤(1+Kn)Fn+1T_n\le (1+Kn)F_{n+1}

Also by induction, we can prove that:

Fn≤2nF_n\le 2^n

So we have:

Tn=O(nFn)=O(n2n)T_n=\mathcal{O}(nF_n)=\mathcal{O}(n2^n)

2.3 Sharper Bounds​

In fact, it can be proven that:

Fn=(1+52)n−(1−52)n5F_n=\frac{(\tfrac{1+\sqrt 5}{2})^n-(\tfrac{1-\sqrt 5}{2})^n}{\sqrt{5}}

So we have:

{Tn=O(n(1+52)n)Tn=Ω((1+52)n)\begin{cases} T_n&=\mathcal{O}\left(n\left(\frac{1+\sqrt 5}{2}\right)^n\right)\\ T_n&=\Omega\left(\left(\frac{1+\sqrt 5}{2}\right)^n\right) \end{cases}

We can do even more than that, using more advanced techniques, it can be established that:

Tn=Θ((1+52)n)T_n=\Theta\left(\left(\frac{1+\sqrt 5}{2}\right)^n\right)

3. Better Solution​

def fibonacci(n:int):
    u,v=(0,1)
    for i in range(n):
        u,v=(v,u+v)
    return u

Let TnT_n be the cost of this algorithm for an input nn:

Tn=Θ(n)T_n=\Theta(n)

4. Fast Solution​

def matMul(A:Mat[p,q],B:Mat[q,r]):
    C:Mat[2,2]=zeros([2,2])
    for i in range(p):
        for j in range(q):
            for k in range(2):
                C[i,j]+=A[i,k]*B[k,j]
   return C


def matPow(A:Mat[p,p],n:int):
    if n == 0:
        return identity([2,2])
    elif n == 1:
        return A
    B=matPow(matMul(B,B),n//2)
    return matMul(B,matPow(A,n%2))

def matVectMul(A:Mat[p,q],u:Vect[q]):
    v:Vect[q]=zeros(q)
    for i in range(p):
        for j in range(q):
            v[i]+=A[i,j]*u[j]
    return v

def fibonacci(n:int):
    F:Mat[2,2]=Mat([[0,1],[1,1]])
    u:Vect[2]=Vect([0,1])
    v=matPow(F,n)*u
    return v[0]

a. Complexity of matMul​

O(pqr)\mathcal{O}(pqr)

b. Complexity of matPow​

O(p3log⁡n)\mathcal{O}(p^3\log n)

c. Complexity of matVectMul​

O(nm)\mathcal{O}(nm)

d. Complexity of fibonacci​

We have p=q=r=2p=q=r=2. So we have the complexity of fibonacci is

Tn=O(p3log⁡n+pq)=O(8log⁡n+4)=O(log⁡n)T_n=\mathcal{O}(p^3\log n+pq)=\mathcal{O}(8\log n+4)=\mathcal{O}(\log n)