Memoization to Optimize Recursion in DSA C - 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 do less work?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int fib(int n, int memo[]) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

// memo array initialized with -1 for all indices

This code calculates Fibonacci numbers using recursion and stores results to avoid repeated work.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to fib with memoization check.
• How many times: Each unique fib(n) is computed once; repeated calls return stored result immediately.

How Execution Grows With Input

Without memoization, calls grow very fast because many repeat. With memoization, each number is calculated once.

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

Pattern observation: The work grows roughly in a straight line with n, not exponentially.

Final Time Complexity

Time Complexity: O(n)

This means the function does work proportional to n, calculating each Fibonacci number once.

Common Mistake

[X] Wrong: "Memoization doesn't change the time complexity; recursion is always slow."

[OK] Correct: Memoization saves results so repeated calls are fast, reducing exponential calls to linear.

Interview Connect

Understanding memoization shows you can improve slow recursive solutions by saving work, a key skill in problem solving.

Self-Check

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