[lukesandberg]

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

[koblenski]

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.