Find Nth Fibbonacci Number

Problem: Find N^th fibonacci number in O(logN) time complexity.
Fibonacci Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

F(n) = F(n-1) + F(n-2)

with initial values: F(0) = 0 and F(1) = 1

For example:

Input: n = 9
Output: 34

Method 1: A simple method that is a direct recursive implementation mathematical recurrence relation given above.

class InterviewDesk
{
    /* method to return required result */
    static int fibonacci(int n)
    {
        /* handling base condition */
        if (n <= 1)
            return n;
        return 
            fibonacci(n-1) + fibonacci(n-2);
    }
     
    /* driver method */
    public static void main (String args[])
    {
        int n = 9;
        System.out.println(fibonacci(n));
    }
}

Output:

34

Time Complexity: Exponential

Method 2: As in above algorithm, we are processing for same sub-problem many times. Hence we follow dynamic approach to avoid calculation of same sub-problem again and again.

class InterviewDesk
{
    /* method to return required result */
    static int Fibonacci(int n)
    {
        int a = 0, b = 1, c;
        
        /* handling base case */
        if (n == 0)
            return a;

        for (int i = 2; i <= n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        
        return b;
    }

    /* driver method */
    public static void main (String args[])
    {
        int n = 9;
        System.out.println(Fibonacci(n));
    }
}

Output:

34

Time Complexity: O(n) and Space Complexity: O(1)

Method 3: Most optimized solution:
We all know the Fibonacci recurrence as F(n+1) = F(n) + F(n-1) but we can represent this in the form a matrix as shown below:

Look at the matrix A = [ [ 1 1 ] [ 1 0 ] ] . Multiplying A with [ F(n) F(n-1) ] gives us [ F(n+1) F(n) ] , so we say that

A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ]

start with [ F(1) F(0) ] , multiplying it with A gives us [ F(2) F(1) ]; again multiplying [ F(2) F(1) ] with A gives us [ F(3) F(2) ] and so on ...

A* [ F(1) F(0) ] = [ F(2) F(1) ]
A* [ F(2) F(1) ] = [ F(3) F(2) ] = A^2 * [ F(1) F(0) ]
A* [ F(3) F(2) ] = [ F(4) F(3) ] = A^3 * [ F(1) F(0) ]
.
.
.
.
A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ] = A^n * [ F(1) F(0) ]

So all that is left is finding the nth power of the matrix A. Well, this can be computed in O(log n) time, by recursive doubling. The idea is, to find A^n , we can do R = A^(n/2) * A^(n/2) and if n is odd, we need do multiply with an A at the end.

Following is the code:

class InterviewDesk
{
    /* method to return required result */
    static int fib(int n)
    {
        int F[][] = new int[][]{{1,1},{1,0}};
        if (n == 0)
            return 0;
        power(F, n-1);
        
        return F[0][0];
    }
     
    /* method to multiply 2 matrices F and M of size 2*2, and
     puts the multiplication result back to F[][] */
    static void multiply(int F[][], int M[][])
    {
        int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
        int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
        int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
        int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
         
        F[0][0] = x;
        F[0][1] = y;
        F[1][0] = z;
        F[1][1] = w;
    }

    /* method that calculates F[][] raise to the power n and puts the
    result in F[][] */
    static void power(int F[][], int n)
    {
        int i;
        int M[][] = new int[][]{{1,1},{1,0}};
        
        /* n - 1 times multiply the matrix to {{1,0},{0,1}} */
        for (i = 2; i <= n; i++)
            multiply(F, M);
    }
     
    /* driver method */
    public static void main (String args[])
    {
        int n = 9;
        System.out.println(fib(n));
    }
}

Output:

34

Time Complexity: O(logn)