News for hackers. Stuff that matters.
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers by dangoldin on Tuesday July 07, 2009 @10:18AM (#691494)
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_e...

Re:On the Linear Time Algorithm For Finding Fibonacci Numbers by cperciva on Tuesday July 07, 2009 @10:27AM (#691508)
Yes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers by dangoldin on Tuesday July 07, 2009 @10:54AM (#691565)
Ah 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.