Re: [Haskell-cafe] Question about memory usage

Roel van Dijk wrote:

On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin 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).

This depends on your definition of "operation". As somebody else pointed out, if you're only dealing with limited-precision arithmetic, you can probably consider all the arithmetic operations to be O(1), in which case the Nth Fibonacci number is O(1). Only if you're dealing with utterly huge numbers do you need to even care about how long it takes to add two numbers. This neatly leads us back to my second assertion: In all my years of computer programming, I've never seen one single program that actually *needs* the Fibonacci numbers in the first place (let alone in arbitrary-precision).