CareerCup

It is the implementation of Fibonacci series 0,1,1,2,3,5,8,13........
F0 =0;
F1 =1;
F2=1;
F3=2;
......
F4=F3+F2;
F4 would 2+1 i.e 3

So u can come up with a C program to implement the fibonacci series which is something like below.

a[1] = 0;
a[2] =1;

for (i=2;i<=n;i++)
{
a[i] = a[i-1]+a[i-2];
printf("%d", a[i]);
}

This has appeared countless times before. O(log n) is possible.

Can you please give the O(log n) solution?

the idea of usign matric multiplication comes from the fact that the fibonacci number f(n) has a relation with the nth exponentition of a 2x2 matrix with all 1 baring the right bottom as zero...and as we know matrix multiplication is essentially divide-n-conquer mechanism, the complexity is just O(logn), HTH

use recursion
=================

function_fib(x){

if(x==0) return 0;
if(x==1) {print 1; return 1;}
if(x==2) {print 2; return 2;}

y=function_fib(x-1)+function_fib(x-2);

print y;

return y;

}



T(n)=T(n/2)+T(n/2) +O(1)
T(n)=2T(n/2) +O(1)

Complexity=O(ln n)

Did u know there was a formula to compute Fib(n)...

Taking r5 = sqrt(5);
f(n) = ( [(1+ r5)/2]^n - [(1- r5)/2]^n )/r5
So basically its an O(1) algorithm !!!

See second ans here for solution
http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

T(n)= T(n-1) + T(n-2)
T(n-1)=T(n-2)+T(n-3)
T(n-2)= T(n-3)+ T(n-4)
Replaceing
T(n)=T(n-2)+ 2T(n-3)+T(n-4)
.......take case of k-1
T(n)= T(n-(k-1))+ (k-1) T(n-((k-1)+1)) + T(n- ((k-1)+2))
we can write this way .. very by keeping k =2

take k=n now
T(n)=T(1)+(n-1) T(0)+ T(1)
T(n)= O(1)

#include<stdio.h>
int fib(int n)
{
  int a = 0, b = 1, c, i;
  if( n == 0)
    return a;
  for (i = 2; i <= n; i++)
  {
     c = a + b;
     a = b;
     b = c;
  }
  return b;
}
 
int main ()
{
  int n = 9;
  printf("%d", fib(n));
  getchar();
  return 0;
}
Time Complexity: O(n)
Extra Space: O(1)