Fibonacci

O(2^n) — Exponential Time

syntax

Each element doubles the work. Common in recursive solutions without memoization.

example

// JavaScript
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}
// Each call branches into 2 → O(2^n)

# Python
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# Fix with memoization → O(n)

output

Time: O(2^n) without memo | O(n) with memo | Space: O(n)

Note Generating all subsets of a set is O(2^n). This is a red flag in interviews — if your solution is exponential, look for overlapping subproblems (DP) or pruning (backtracking). Always mention that memoization brings it down.

Memoization vs Tabulation

DSA · Dynamic Programming

syntax

Memoization (top-down): Recursive + cache results of subproblems.
Tabulation (bottom-up): Iterative + fill a table from base cases up.
Both avoid recomputing overlapping subproblems.

example

// JavaScript — Fibonacci both ways
// Top-down (memoization)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

// Bottom-up (tabulation)
function fibTab(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

# Python
# Top-down
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Bottom-up
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

output

fib_memo(10) → 55
fib_tab(10) → 55

Note Both are O(n) time, O(n) space. Memoization is easier to write (natural recursion) but has call stack overhead. Tabulation avoids stack overflow and can be space-optimized (keep only last 2 values → O(1) space). Start with memoization in interviews, then optimize to tabulation if asked.

DSAInterview Prep