Fibonacci — Iterative and Memoized

📌 Definition:

📖 Detailed Explanation:

Naive recursion is O(2^n) — exponential and unusable beyond ~40. The iterative bottom-up version is O(n) time O(1) space; memoization caches subresults to make recursion O(n).

💻 Solutions:

• JavaScript

// Iterative — O(n) time, O(1) space
function fib(n) {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

// Memoized recursion
function fibMemo(n, memo = {}) {
  if (n < 2) return n;
  if (memo[n] !== undefined) return memo[n];
  return (memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo));
}

🔑 Key Points:

• Naive recursion is O(2^n) — recomputes the same values
• Iterative is O(n) time, O(1) space
• Memoization caches subproblems → O(n)
• [a, b] = [b, a+b] swaps without a temp

🌍 Real-World Example: