3 ms·
There's a closed form solution to calculate the Nth Fibonacci number which can be derived from a recurrence relation. http://en.wikipedia.org/wiki/Fibonacci_Nu
by dangoldin 17y ago
There's a closed form solution to calculate the Nth Fibonacci number which can be derived from a recurrence relation.
http://en.wikipedia.org/wiki/Fibonacci_Numbers#Closed_form_expression http://en.wikipedia.org/wiki/Fibonacci_Numbers#Closed_form_e...
- cperciva 17y agoYes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.
- dangoldin 17y agoAh my mistake then. I didn't realize the closed form solution takes that long to evaluate. Couldn't there be a faster way to evaluate it using an algebraic rather than a computational way? I just find the bound you give too high but I may be completely wrong.