Memoization Top Down DP in DSA Typescript - Time & Space Complexity

Time Complexity: Memoization Top Down DP

O(n)

Understanding Time Complexity

We want to understand how using memoization in top-down dynamic programming changes the time it takes to solve problems.

Specifically, how does remembering past answers speed up repeated calculations?

Scenario Under Consideration

Analyze the time complexity of the following memoized Fibonacci function.

function fib(n: number, memo: 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 work.

Identify Repeating Operations

Look for repeated calculations and how memoization affects them.

• Primary operation: Recursive calls to fib for smaller n.
• How many times: Without memo, calls grow exponentially; with memo, each n is computed once.

How Execution Grows With Input

With memoization, each number from 0 up to n is calculated once and stored.

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

Pattern observation: The number of operations grows roughly in a straight line with n.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute fib(n) grows linearly with n because each value is computed once and reused.

Common Mistake

[X] Wrong: "Memoization still makes the function exponential because of recursion."

[OK] Correct: Memoization stores results, so each input is solved once, preventing repeated exponential calls.

Interview Connect

Understanding memoization shows you can optimize recursive solutions by saving work, a key skill in many coding problems.

Self-Check

"What if we removed memoization? How would the time complexity change?"