Andrew Coppin andrewcoppin at btinternet.com
Mon Aug 16 14:37:55 EDT 2010

```Roel van Dijk wrote:
> On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
> <andrewcoppin at btinternet.com> wrote:
>
>>  (Then again, the Fibonacci numbers can be computed
>> in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so
>> this is obviously example code.)
>>
>
> A bit off-topic, but I don't think there exists a function that
> computes fibonacci numbers in O(1) time. There exists a closed-form
> expression to calculate the nth Fibonacci number, but the complexity
> of that expression is not O(1):
>
> phi = (1 + sqrt 5) / 2
> fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5
>
> The use of (**) should make the complexity at least O(n). Please
> correct me if I'm wrong (or sloppy).
>

This depends on your definition of "operation".

As somebody else pointed out, if you're only dealing with
limited-precision arithmetic, you can probably consider all the
arithmetic operations to be O(1), in which case the Nth Fibonacci number
is O(1). Only if you're dealing with utterly huge numbers do you need to