Memoization to Optimize Recursion in DSA Typescript - Time & Space Complexity

Time Complexity: Memoization to Optimize Recursion

O(n)

Understanding Time Complexity

We want to see how using memoization changes the speed of recursive functions.

How does remembering past answers help us avoid repeating work?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function fib(n: number, memo: Record<number, number> = {}): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
    

This function calculates the nth Fibonacci number using recursion and stores results to avoid repeated calculations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to fib with smaller n.
• How many times: Each unique n from 0 to n is computed once due to memoization.

How Execution Grows With Input

Each number from 0 up to n is calculated once and stored, so work grows steadily with n.

Input Size (n)	Approx. Operations
10	About 10 calculations
100	About 100 calculations
1000	About 1000 calculations

Pattern observation: The work grows roughly in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the function does work proportional to the input size, calculating each needed value once.

Common Mistake

[X] Wrong: "Recursive Fibonacci always takes exponential time because it calls itself twice each time."

[OK] Correct: With memoization, each number is calculated once and saved, so repeated calls don't redo work, making it much faster.

Interview Connect

Understanding how memoization changes recursion speed is a key skill that shows you can improve algorithms by avoiding repeated work.

Self-Check

"What if we removed memoization and just used plain recursion? How would the time complexity change?"