[Haskell-cafe] Question about memory usage

Roel van Dijk vandijk.roel at gmail.com
Mon Aug 16 08:37:34 EDT 2010

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


More information about the Haskell-Cafe mailing list