Fibonacci numbers
FROM
time complexity : O(lgN)idea
F2n-1 = Fn^2 + (Fn-1)^2F2n = (2*Fn-1 + Fn)*Fn If n is even then k = n/2:F(n) = [2*F(k-1) + F(k)]*F(k)If n is odd then k = (n + 1)/2F(n) = F(k)*F(k) + F(k-1)*F(k-1)
Fibonacci numbersFROM
time complexity : O(lgN)idea
F2n-1 = Fn^2 + (Fn-1)^2F2n = (2*Fn-1 + Fn)*Fn If n is even then k = n/2:F(n) = [2*F(k-1) + F(k)]*F(k)If n is odd then k = (n + 1)/2F(n) = F(k)*F(k) + F(k-1)*F(k-1)