Fibonacci numbers

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

with seed values

 Using power of the matrix {{1,1},{1,0}}  ( log(n) solution)

This another fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.

The matrix representation gives the following closed expression for the Fibonacci numbers:

#include <stdio.h> void multiply(int F[2][2], int M[2][2]); void power(int F[2][2], int n); /* function that returns nth Fibonacci number */ int fib(int n) {   int F[2][2] = {{1,1},{1,0}};   if (n == 0)     return 0;   power(F, n-1);   return F[0][0]; } /* Optimized version of power() in method 4 */ void power(int F[2][2], int n) {   if( n == 0 || n == 1)       return;   int M[2][2] = {{1,1},{1,0}};   power(F, n/2);   multiply(F, F);   if (n%2 != 0)      multiply(F, M); } void multiply(int F[2][2], int M[2][2]) {   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; } /* Driver program to test above function */ int main() {   int n = 9;   printf("%d", fib(9));   getchar();   return 0; }

Time Complexity: O(Logn)
Extra Space: O(Logn) if we consider the function call stack size, otherwise O(1).