4 ms·

Why not calculate it in constant time ? https://artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula https://artofproblemsolving.com/wiki/index.php?t

• edflsafoiewq 8y ago
  You can't really compute it in constant time since the number of bits in the nth Fibonacci number is O(n), so you need to take at least that long just to write the result out. Computing with Binet's formula is also rather tricky. You just need to round φ^n/√5, but how many bits of √5 do you need to use?
  • toolslive 8y ago
    true: adding 2 64 bit numbers is constant time for me, but adding 2 4096 bit numbers is not. Eventually, even the simplest operation becomes O(ln n)
• braythwayt 8y ago
  As mentioned in other comments, working with floating point numbers in practice is trickier than it looks in theory: http://raganwald.com/2013/03/26/the-interview.html http://raganwald.com/2013/03/26/the-interview.html