Goldman Sachs Interview Question
Software Engineer / Developersthe 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)
Incorrect.
Infact: T(n)=T(n-1)+T(n-2)
and T(n-1) != T(n/2) unless n = 1
So ur conclusion is incorrect
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)
It is the implementation of Fibonacci series 0,1,1,2,3,5,8,13........
- Anonymous July 01, 2009F0 =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]);
}