Question

2) In class we showed a Matrix algorithm for Fibonacci numbers: 1 112 1 0 n+1 F (Note: No credit for an induction proof that this is true. I'm not asking that.) a) What is the running time for this algorithm? (3 pts.) b) Prove it. (9 pts.)

Answer 1

Algorithm:

mul(a[2][2],b[2][2]) //function to multiply 2 2x2 matrix
{
x<-a[0][0]*b[0][0]+a[0][1]*b[1][0]
y<-a[0][0]*b[0][1]+a[0][1]*b[1][1]
z<-a[1][0]*b[0][0]+a[1][1]*b[1][0]
w<-a[1][0]*b[0][1]+a[1][1]*b[1][1]
a[0][0] <- x
a[0][1] <- y
a[1][0] <- z
a[1][1] <- w
}

fibcalc(a[2][2], n)
{
b[2][2] <- {{1,1},{1,0}}
for i<-2 to n
     mul(a,b)
}

fibonacci(n)
{
a[2][2] <- {{1,1},{1,0}}
if n=0
    return 0;
fibcalc(a,n-1)
return a
}

Time complexity = O(n)

Explanation:

In this Algorithm, there is a main function fibonacci which calls another function just once namely fibcalc.

fibacalc is the recursive function that calls itself n times and the main basic operation performed by it is calculation of two matrices which has a timee period T(1).

T(n) = T(fibcalc(a,n-1))

T(n) = T(1) + T(fibcalc(a,n-2))

T(n) = T(1) + T(1) + ...... + T(fibcalc(a,0)) [n-n=0, this will happen n times]

T(n) = O(n) [T(1) *n = O(n)]