Find nth Fibonacci number --> Binet's Formula (Time = O(1) ??)

 So title might have make you focus on this topic  and  also you are thinking of that is it really possible?

Yes it is.but not for every value of n, let's see more about in this post.

So first what is fibonacci sequence ?

0 1 1 2 3 5 8 13 .............. (sum of every first and second number = every third number)

if you are interested in fibonacci even more then you can find out more detail here

first let's discuss what are other way of getting nth fibonacci number?(here i am using c++)

Method 1: Recursion

    int fib(int N) {
        if(N == 0)  return 0; 
        if(N == 1)  return 1;
        return fib(N-1) + fib(N-2);
    }

Time Complexity : O(2^N)

Space Complexity :  O(N) (because of function call stack size)

Method 2 :  DP with Memoization

int fib(int N) {

if(N < 2)

return N;

int memo[N+2];

memo[0] = 0;

memo[1] = 1;

for(int i=2; i<=N; i++)

memo[i] = memo[i-1] + memo[i-2];

return memo[N];

}

Time Complexity : O(N)

Space Complexity : O(N)

Method 3 : DP

int fib(int N) {

if(N < 2)

return N;

int a = 0, b = 1, c = 0;

for(int i = 1; i < N; i++)

{

c = a + b;

a = b;

b = c;

}

return c;

}

Time Complexity : O(N)

Space Complexity : O(1)

Method 4: Binet's Fiibonacci number formula

Real formula is : (pow(1+sqrt(5),n)- pow(1-sqrt(5),n) /pow(2,n*sqrt(5)))

but for we'll use little small formula for program you can use above formula too.

this method won't give perfect result for too large value of N

int fib(int N) {

double phi = (sqrt(5) + 1) / 2;

return round(pow(phi, N) / sqrt(5));

}

Time Complexity : O(1)

Space Complexity : O(1)

If you want to know more about binet's Formula for nth fibonacci number it's here

Note: above shown time complexity is according to c++ becuase for c++ pow() takes O(1) (also depend on architecture) more detail is here . for some programming language it uses log(N)

If you have any thoughts feel free to share in comment section.

Thank You 😊😊