Optimizing Program for Fibonacci Series (Optimizing Algorithm/Program Step by Step)

Problem:
F(0)=0;
F(1)=1;
F (n)=(F(n-1)+F(n-2)) mod 10
efficient algorithm that computes this function.


Algo I :

int rec (int n){
    if (n<2)
     return (n);
   else
     return((rec(n-1)+rec(n-2))%10);

}


Exponential time

Linear Space

Algo II : 

int dp (int n){
f[0]=0;
f[1]=1;
for (i=2;i<=n; ++i)
f [n] =(f[n-1]+f[n-2])%10;
}

Linear time.
Linear space.

Algo III:

int linear (int n){
a=0; b=1; c=n;
for (i=2;i<=n; ++i){
c=(a+b)%10;
a=b;
b=c;
}
return c;
}

Linear time.
Constant space.

Algo IV:

For further optimization, we should analyse the output sequence and check whether it is periodic or not.
If it is periodic @ x then find value till x and use (n mod x ) to compute nth term of series.
e.g, Fibonacci series is periodic (not known exactly but 'x' is between 61-72).