   How to find the Nth Fibonacci number in O(log N) time complexity?

+1 vote
119 views
How to find the Nth Fibonacci number in O(log N) time complexity? posted Dec 18, 2015

+1 vote

another way of calculating N'th Fibonacci number is to take a base matrix F={{1,1},{1,0}} and multiply it recursively. In this scenario suppose we wan to calculate Fibonacci of number 9,then power(F,n-1) will be called 4 times (power(F,8)->power(F,4)->power(F,4)->power(F,2) once n==1 or n==0 "return" statement will be executed and matrix F will start to multiply 4 times recursively, after that all you need to do is to print the number at F position,which in this particular scenario is 34. complexity is O(log n).

``````#include <stdio.h>

void multiply(int F, int M);

void power(int F, int n);

/* function that returns nth Fibonacci number */
int fib(int n)
{
int F = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F;
}

/* Optimized version of power() in method 4 */
void power(int F, int n)
{
if( n == 0 || n == 1)
return;
int M = {{1,1},{1,0}};

power(F, n/2);
multiply(F, F);

if (n%2 != 0)
multiply(F, M);
}

void multiply(int F, int M)
{
int x =  F*M + F*M;
int y =  F*M + F*M;
int z =  F*M + F*M;
int w =  F*M + F*M;

F = x;
F = y;
F = z;
F = w;
}

/* Driver program to test above function */
int main()
{
int n;
scanf("%d",&n);
printf("%d", fib(n));
getchar();
return 0;
}
`````` answer Mar 20, 2016
``````#include<stdio.h>
#include<stdlib.h>

void main()
{
int n;
int *arr;
int i;

printf("enter the number:: ");
scanf("%d",&n);

arr=(int *)malloc(sizeof(int)*n);
arr=0;
arr=1;

for(i=2;i<n;i++)
{
arr[i]=arr[i-1]+arr[i-2];
}

for(i=0;i<n;i++)
printf("%d\t",arr[i]);

free(arr);
}
`````` answer Dec 20, 2015
This is of O(n) complexity not the O(log n), do you like to correct your solution? answer Dec 20, 2015