4 ms·

Speaking of Fibionacci, I was browsing through my old Data Structures and Algorithms lecture notes the other day for nostalgia and discovered that Fibionacci(n)

• 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 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 ago
      Oh, 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 ago
      Which is O(phi^n).