The Misuse of Recursion

http://sam-koblenski.blogspot.com/2013/04/the-misuse-of-recursion.html

by koblenski • 13 years ago

2 4 13 years ago

sam-koblenski.blogspot.com

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...

koblenski2• 13 years ago

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.

lukesandberg2• 13 years ago

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).

The Misuse of Recursion

Related Stories