4 ms·
A closed-form solution exists, so if you pretend that arithmetic is free, it's O(1)! Bignum multiplication is significantly slower than bignum addition; if mem
by camccann 17y ago
A closed-form solution exists, so if you pretend that arithmetic is free, it's O(1)!
Bignum multiplication is significantly slower than bignum addition; if memory serves me it ends up coming out that you're essentially stuck with O(n^2) no matter what you do.
Fun fact: The naive, unmemoized recursive Fibonacci function has time complexity of precisely O(fib(n)). Scary!
- shrughes 17y agoOh, I'm sorry, I was under the impression that there existed O(N log N) multiplication algorithms, but apparently that's just conjectured. Right now the best seems to be O(N log(N) 2^(log*(N))) ( http://en.wikipedia.org/wiki/Fürers_algorithm http://en.wikipedia.org/wiki/Fürers_algorithm ), which is slightly better than O(N log N log log N). Okay then. Also, the closed form solution would still be O(log N), since I don't think anybody yet considers exponentiation to be free :-)
- spicyj 17y agoWhich is O(phi^n).