[Haskell-cafe] Question about memory usage

[Roel van Dijk]

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

Regards,
Roel