Hacker News Reader

The title is wrong -- it should be "On the Quadratic Time Algorithm...". The fastest algorithm of which I'm aware is O(n log n 2^log*(n)); and I'd be astonished if it were possible to compute the nth fibonacci number in o(n log n) time, although I can't offhand see any way to prove that it is impossible.

View on HN

The title mimicks the common misunderstanding that naive calculation for Fibonacci numbers is done in linear time, which is not true when cost of arithmetic operations is not negligible. The whole point of the article, as I understand it, was to show that not taking such details in account will lead to flawed analysis.

That's right!

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

Yes, and the fastest algorithm I know to evaluate that expression takes O(n log n 2^log*(n)) time.

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.

Reply on news.ycombinator.com