LeetCode #509 Fibonacci Number with JavaScript

Solutions to LeetCode's 509. Fibonacci Number with JavaScript.

Solution 1: Recursive

/**
 * @param {number} n
 * @return {number}
 */
const fib = (n) => {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fib(n - 1) + fib(n - 2);
};

• Time complexity: O(2^n)
• Space complexity: O(n)

This code is simple and easy to read, but it is not suitable for cases where the argument n has a large value because the time complexity is O(2^n).

Solution 2: Iterative

/**
 * @param {number} n
 * @return {number}
 */
const fib = (n) => {
  let fibSequence = [0, 1];
  for (let i = 2; i <= n; i++) {
    fibSequence.push(fibSequence[i - 1] + fibSequence[i - 2]);
  }
  return fibSequence[n];
};

• Time complexity: O(n)
• Space complexity: O(n)

It is less readable than recursive, but the time complexity is O(n), so if there is a possibility of large values in the argument n, this is better.