Each element doubles the work.Commonin recursive solutions without memoization.
Example
// JavaScriptfunctionfibNaive(n){if(n <=1)return n;returnfibNaive(n -1)+fibNaive(n -2);}// Each call branches into 2 → O(2^n)
# Python
def fib_naive(n):if n <=1:return n
returnfib_naive(n -1)+fib_naive(n -2)
# Fixwith 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(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)functionfibMemo(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)functionfibTab(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 inrange(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.
Frequently asked questions
How does Interview Prep handle fibonacci?
Interview Prep covers this with 2 copy-ready snippets on this page. The "O(2^n) - Exponential Time" snippet in Interview Prep uses `Each element doubles the work. Common in recursive solutions without memoization.`.
Which code does the Interview Prep example use?
The "O(2^n) - Exponential Time" snippet uses `Each element doubles the work. Common in recursive solutions without memoization.`, from the Big-O Notation section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "fibonacci"?
Besides "O(2^n) - Exponential Time", this page also shows "Memoization vs Tabulation".
Is there anything to watch out for?
Yes. For "O(2^n) - Exponential Time": 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.