The Misuse of Recursion

sam-koblenski.blogspot.com

2 points·koblenski··4 comments

I was a little disappointed that he didn't point out that there is an O(1) formula for fibonacci numbers. http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

That is a closed form expression, but it is not O(1) unless the processor can raise a number (an inexact floating point number, no less) to a power in constant time. The closed form expression is still O(n) because of multiplication, and the result isn't an exact number unless the constants are run out to enough precision for the value of n that is being computed.

There is a rounding formula that should make it possible to implement efficiently in inexact floating point arithmetic. (I think knuth gives a solution in TAOCP).

Also, depending on how you are accounting for the 'size of n', the iterative algorithm has time O(2^b) where b is the number of bits required to represent n and the closed form is O(b).

There's a fascinating discussion of this on stackoverflow: http://stackoverflow.com/questions/1525521/nth-fibonacci-num...

If you want an exact value for a particular Fibonacci number, it will take at least O(n) time regardless of the algorithm used because a Fibonacci number 'n' has O(n) digits, and it will take O(n) time to clear and set the memory for that number. In any case, there is no O(1) algorithm. There is an O(ln n) algorithm for small 'n' for which the result will fit within the processor's native data types.

I had not thought that Fibonacci numbers increased quite that rapidly, but after thinking about it, it makes sense.

Reply on news.ycombinator.com