|
|
|
|
|
|
by koblenski
4686 days ago
|
|
|
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. |
|
|