Search code examples
performancealgorithmmathtime-complexityfibonacci

nth fibonacci number in sublinear time

Is there any algorithm to compute the nth fibonacci number in sub linear time?

Solution

  • The nth Fibonacci number is given by

    f(n) = Floor(phi^n / sqrt(5) + 1/2)

    where 

    phi = (1 + sqrt(5)) / 2

    Assuming that the primitive mathematical operations (+, -, * and /) are O(1) you can use this result to compute the nth Fibonacci number in O(log n) time (O(log n) because of the exponentiation in the formula).

    In C#:

    static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}