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

Time Complexity: Memoization Top Down DP

O(n)

Understanding Time Complexity

We analyze how memoization in top-down dynamic programming reduces repeated work.

We want to know how the number of operations changes as input size grows.

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];
}

This code calculates the nth Fibonacci number using recursion with memoization to store results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to fib with memo checks.
• How many times: Each unique fib(n) is computed once; repeated calls return stored results instantly.

How Execution Grows With Input

Each number from 0 to n is computed once, so operations grow roughly in a straight line with n.

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

Pattern observation: Doubling n roughly doubles the work, showing linear growth.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows in direct proportion to the input size n.

Common Mistake

[X] Wrong: "Memoization still does all recursive calls like plain recursion."

[OK] Correct: Memoization stores results, so each unique call runs once, avoiding repeated work.

Interview Connect

Understanding memoization's time savings shows you can optimize slow recursive solutions effectively.

Self-Check

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