4 ms·
Only if you ignore the cost of multiplication or the size of the numbers involved. The length of the answer is proportional to N, so you end up with N log N ti
by shrughes 17y ago
Only if you ignore the cost of multiplication or the size of the numbers involved. The length of the answer is proportional to N, so you end up with N log N time with the typical exponentiating algorithm, and there's no way you'll beat linear time. The regular old additive for loop takes N^2 time, though.
- camccann 17y agoA 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).