top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

3 Answers

+1 vote

another way of calculating N'th Fibonacci number is to take a base matrix F[2][2]={{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[2][2] will start to multiply 4 times recursively, after that all you need to do is to print the number at F[0][0] position,which in this particular scenario is 34. complexity is O(log n).

#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;
  scanf("%d",&n);
  printf("%d", fib(n));
  getchar();
  return 0;
}
answer Mar 20, 2016 by Shahsikant Dwivedi
0 votes
#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]=0;
    arr[1]=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 by Shishir Chaudhary
This is of O(n) complexity not the O(log n), do you like to correct your solution?
0 votes

A Fibonacci number series has special property which is increasing order series means we can say this is sorted order series.So for finding and element in the series in O(log n) time,We can use Binary search on the given series.
Hence we know to search an element in the list through Binary search takes O(log n) time.

answer Dec 20, 2015 by Rajan Paswan
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...