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

Question

While reading possible time complexity i found that time complexity O(log log n) exist for some algos,

Can any one explain an example which shows the calculation of the time complexity with O(log log n)

Answer 1

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 2

#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);
}

Comments

This is of O(n) complexity not the O(log n), do you like to correct your solution?

Answer 3

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.