/**
 * Recursively computes the nth fibonachi #. This method is super slow because
 * there is a tonnn of duplicated work.
 *
 * runtime: O(n*(n-1)(n-2) + n(n-2)) = O(n^2)
 *
 * @param {number} n
 * @return {number}
 */
function naiveFibonachi(n) {
  if (n <= 1) {
    return n;
  }

  return naiveFibonachi(n - 1) + naiveFibonachi(n - 2);
}

/**
 * memoized naive fibonachi is much better but still overly complicated
 *
 * runtime: O(n)
 *
 * @param {number} n
 * @return {number}
 */
function memoizedNaiveFibonachi(n) {
  fibonachi.visited = fibonachi.visited || new Array(n);

  if (n <= 1) {
    fibonachi.visited[n] = n;

    return n;
  } else if (fibonachi.visited[n]) {
    return fibonachi.visited[n];
  }

  fibonachi.visited[n] = fibonachi(n - 1) + fibonachi(n - 2);

  return fibonachi.visited[n];
}

/**
 * operations: ~ 6n + 4
 *
 * runtime: O(n)
 *
 * @param {number} n
 * @return {number}
 */
function fastSimpleFibonachi(n) {
  const sequence = new Array(n);    // ~ 1 operation (1x assignment)
  sequence[0] = 0;                  // ~ 1 operation (1x assignment)
  sequence[1] = 1;                  // ~ 1 operation (1x assignment)

  for (let i = 2; i < n; i++) {                  // ~ 2 operations (1x guard, 1x increment)
    sequence[i] = sequence[i-1] + sequence[i-2]; // ~ 4 operations (1x assignment, 2x access, 1x addition)
  }

  return sequence[n - 1];           // ~ 1 operation (1x access)
}