3 ms·
And since exponentation is logarithmic in the exponent, this algorithm is computing Fib(n) in O(log n) time. So while more compact than the matrix method or the
by andrewla 3y ago
And since exponentation is logarithmic in the exponent, this algorithm is computing Fib(n) in O(log n) time. So while more compact than the matrix method or the field extension method or the doubling formula method, this reduces to the same complexity.
I'd venture to say that it is clear that we can't really do better than O(log n) just because the number of digits in Fib(n) is O(log n).
- marschot 3y agoThe number of bits in Fib(n) is O(n), not O(log n). Put differently, Fib(n) grows exponentially. To be precise, Fib(n) = (phi^n - (-phi)^(-n)) / sqrt(5). So the complexity to compute Fib(n) is O(n) time (or slower). And one algorithm that runs this fast is to compute the n-th power of [[1,1],[1,0]] (using repeated squaring and large integer arithmetic).
- andrewla 3y agoI stand corrected. I made the same mistake that I am attributing to others; to think that n-bit arithmetic operations are O(1) instead of O(n).