re: A common recursion interview challenge VIEW POST


Nice series!
Would like to share for others that the nth Fibonacci number can be calculated in O(1) with the Binet Formula as I’ve learned it recently too.
Here’s my version of it:

 * Binet's Formula - Calculate the Fib of the nth 'n' term
const fibOfN = n => {
  const { pow, sqrt, floor } = Math;
  const Phi = (sqrt(5) + 1) / 2;
  const fibOfN = (pow(Phi, n) - pow(-Phi, -n)) / sqrt(5);
  return floor(fibOfN);
Code of Conduct Report abuse