3 ms·
It’s cheating (or at best misleading) to allow arbitrarily expensive operations to be considered “constant time”. Raising a very-high-precision approximation o
by jacobolus 8y ago
It’s cheating (or at best misleading) to allow arbitrarily expensive operations to be considered “constant time”.
Raising a very-high-precision approximation of an irrational number to a large integer power will get slower and slower as you handle larger numbers.
You might just as well call the matrix version O(1)
- TheRealPomax 8y agoNot sure if you noticed that's literally what they did at the end of the "Eigenvalue Solution" section, but it reads "So there you have it – a O(1) algorithm for any Fibonacci number." Although they do note that eigen_fib() completely breaks down once the numbers involved are larger than fit in a 64 bit integer.
- jacobolus 8y agoThe previous commenter was criticizing https://www.nayuki.io/page/fast-fibonacci-algorithms https://www.nayuki.io/page/fast-fibonacci-algorithms (for not mentioning the supposedly O(1) solution) not http://www.oranlooney.com/post/fibonacci/ http://www.oranlooney.com/post/fibonacci/