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

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);
}

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)!

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;
}