DEV Community

Discussion on: A common recursion interview challenge

Collapse
 
alexparra profile image
Alex Parra

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);
};
Collapse
 
elisabethgross profile image
elisabethgross

Nice!