[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).
Regards,
Roel
More information about the Haskell-Cafe
mailing list