On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin <[email protected]> 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
