16 Aug
2010
16 Aug
'10
8:37 a.m.
On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
(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