Fibonacci Series

1// 1. Bottom-Up Tabulation with O(1) Constant Auxiliary Space
2function fibonacci(n) {
3  if (n <= 0) return 0;
4  if (n === 1) return 1;
5 
6  let prev2 = 0; // F(0)
7  let prev1 = 1; // F(1)
8  let current = 0;
9 
10  for (let i = 2; i <= n; i++) {
11    current = prev1 + prev2;
12    prev2 = prev1;
13    prev1 = current;
14  }
15 
16  return current;
17}
18 
19// 2. Top-Down Memoization (Linear O(n) Space for recursion stack & cache)
20function fibMemo(n, memo = {}) {
21  if (n <= 0) return 0;
22  if (n === 1) return 1;
23  if (memo[n] !== undefined) return memo[n];
24 
25  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
26  return memo[n];
27}
28 
29// Example usage:
30// fibonacci(10); // 55
31// fibMemo(10);    // 55