Can a Fibonacci function be written to execute in O(1) time?

Question

So, we see a lot of fibonacci questions. I, personally, hate them. A lot. More than a lot. I thought it'd be neat if maybe we could make it impossible for anyone to ever use it as an interview question again. Let's see how close to O(1) we can get fibonacci.

Here's my kick off, pretty much crib'd from Wikipedia, with of course plenty of headroom. Importantly, this solution will detonate for any particularly large fib, and it contains a relatively naive use of the power function, which places it at O(log(n)) at worst, if your libraries aren't good. I suspect we can get rid of the power function, or at least specialize it. Anyone up for helping? Is there a true O(1) solution, other than the finite* solution of using a look-up table?

http://ideone.com/FDt3P

#include <iostream>
#include <math.h>
using namespace std; // would never normally do this.
     
int main() {
    int target = 10;
    cin >> target;
    // should be close enough for anything that won't make us explode anyway.
    float mangle = 2.23607610; 
     
    float manglemore = mangle;
    ++manglemore; manglemore = manglemore / 2;
    manglemore = pow(manglemore, target);
    manglemore = manglemore/mangle;
    manglemore += .5;
    cout << floor(manglemore);
}

*I know, I know, it's enough for any of the zero practical uses fibonacci has.

Answer 1

Here is a near O(1) solution for a Fibonacci sequence term. Admittedly, O(log n) depending on the system Math.pow() implementation, but it is Fibonacci w/o a visible loop, if your interviewer is looking for that. The ceil() was due to rounding precision on larger values returning .9 repeating.

Example in JS:

function fib (n) {
  var A=(1+Math.sqrt(5))/2,
      B=(1-Math.sqrt(5))/2,
      fib = (Math.pow(A,n) - Math.pow(B,n)) / Math.sqrt(5);
      return Math.ceil(fib);
}

Answer 2

Given arbitrary large inputs, simply reading in n takes O(log n), so in that sense no constant time algorithm is possible. So, use the closed form solution, or precompute the values you care about, to get reasonable performance.

Edit: In comments it was pointed out that it is actually worse, because fibonacci is O(phi^n) printing the result of Fibonacci is O(log (phi^n)) which is O(n)!

Answer 3

The following answer executes in O(1), though I am not sure whether it is qualified for you question. It is called Template Meta-Programming.

#include <iostream>
using namespace std;

template <int N>
class Fibonacci
{
public:
    enum {
        value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value
    };
};

template <>
class Fibonacci<0>
{
public:
    enum {
        value = 0
    };
};

template <>
class Fibonacci<1>
{
public:
    enum {
        value = 1
    };
};

int main()
{
    cout << Fibonacci<50>::value << endl;
    return 0;
}

Answer 4

In Programming: The Derivation of Algorithms, Anne Kaldewaij expands out the linear algebra solution to get (translated and refactored from the programming language used in that book):

template <typename Int_t> Int_t fib(Int_t n)
{
    Int_t a = 0, b = 1, x = 0, y 1, t0, t1;
    while (n != 0) {
        switch(n % 2) {
            case 1:
                t0 = a * x + b * y;
                t1 = b * x + a * y + b * y;
                x = t0;
                y = t1;
                --n;
                continue;
            default:
                t0 = a * a + b * b;
                t1 = 2 * a * b + b * b;
                a = t0;
                b = t1;
                n /= 2;
                continue;
        }
    }
    return x;
}

This has O(log n) complexity. That's not constant, of course, but I think it's worth adding to the discussion, especially given that it only uses relatively fast integer operations and has no possibility of rounding error.

Answer 5

Yes. Precalculate the values, and store in an array, then use N to do a lookup.

Answer 6

Pick some largest value to handle. For any larger value, raise an error. For any smaller value than that, just store the answer at that smaller value, and keep running the calculation for the "largest" value, and return the stored value.

After all, O(1) specifically means "constant", not "fast". With this method, all calculations will take the same amount of time.

Answer 7

Fibonacci in O(1) space and time (Python implementation):

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

def fib(n: int):
  return int(PHI ** n / sqrt(5) + 0.5)