Fibonacci Numbers are

Fibonacci numbers are generated using the following recurrence relation

It is interesting to note that the Fibonacci number grows so fast that exceeds the 32-bit signed integer range.

The fastest way to accurately compute Fibonacci numbers is by using a matrix-exponentiation method.

We need to calculate to calculate the N^th fibonacci number. We can calculate it in using fast exponentiation.

Simple Recursive Solution

fibonacci(n)
    if(n=0)
        return 0
    if (n=1)
        return 1
    return (fibonacci(n-1)+fibonacci(n-2))

Time complexity:

Optimization using Dynamic Programming

There are only n overlapping subproblems which can be stored to reduce the time complexity to

//Initialize all elements in dp to -1
fibonacci(n)
    if(dp[n]!=-1)
        return dp[n]
    if(n=0)
        dp[n]=0
    else if (n=1)
        dp[n]=1
    else
        dp[n]=fibonacci(n-1)+fibonacci(n-2)  
    return dp[n]

Time Complexity =
Space Complexity =

Using Matrix Exponentiation

//Calculating A^p in O(log(P))
Matrix_pow ( Matrix A,int p )
    if(p=1)
        return A
    if(p%2=1)
        return A*Matrix_pow(A,p-1)  

    Matrix B = Matrix_pow(a,p/2);
    return B * B

fibonacci(n)
    if(n=0)
        return 0;
    if(n=1)
        return 1;
    Matrix M[2][2]={{1,1},{1,0}}
    Matrix res=matrix_pow(M,n-1);
    return res[0][0];

Time Complexity =

According to Binet's formula, a Fibonacci number is given by

where, and

solving for gives

This formula must return an integer for all , so the expression under the radical must be an integer (otherwise, the logarithm does not even return a rational number).

Hence, for to be a Fibonacci number, or must be a perfect square.

Precomputation is a technique where we try to use memory to store solutions in advance, such as values that are computed multiple times in a challenge, so that they can be converted to a memory look up.

Clearly lookups are in complexity and hence reduce the time of computation overall to a great extent.

For example, suppose there are 10,000 queries on finding . If we precalculate factorials this task becomes a O(1) as we just have to multiply and divide. Otherwise we have to do it in O(n) every time.