4 ms·
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 astonishe
by cperciva 17y ago
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.
- vang3lis 17y agoThe 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.
- pkrumins 17y agoThat's right!
- dangoldin 17y agoThere'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.
- deleted 17y ago[deleted]