Binet's formula doesn't run in O(1) if you want an exact answer. Using a + b * sqrt(5) representations or floating point with sufficient precision, you can get O(n log n 2^O(log* n)) time (quoting Wikipedia's Furer's algorithm page here). Which beats O(n log n log log n) time, if you were wondering. If something beats that for computing Fibonacci numbers, that'd be pretty cool.