Overlapping Subproblems and Optimal Substructure in DSA C - Time & Space Complexity

Time Complexity: Overlapping Subproblems and Optimal Substructure

O(n)

Understanding Time Complexity

We want to understand how solving problems with repeated parts affects the time it takes.

How does breaking a problem into smaller parts and reusing answers change the work needed?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

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

This code calculates Fibonacci numbers using simple recursion and recursion with memoization to avoid repeated work.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to fib or fib_memo functions.
• How many times: In simple recursion, many calls repeat the same calculations; in memoized version, each unique call happens once.

How Execution Grows With Input

Without memoization, the calls grow very fast because the same problems are solved many times.

Input Size (n)	Approx. Operations (simple recursion)
10	~177 calls
20	~21,891 calls
30	~2,692,537 calls

With memoization, the number of calls grows only linearly with n because each result is stored and reused.

Input Size (n)	Approx. Operations (memoized)
10	10 calls
20	20 calls
30	30 calls

Pattern observation: Simple recursion grows exponentially, memoized recursion grows linearly.

Final Time Complexity

Time Complexity: O(n) with memoization

This means the work grows in a straight line with input size when we reuse answers, avoiding repeated work.

Common Mistake

[X] Wrong: "Recursion always means exponential time because it calls itself many times."

[OK] Correct: When we save results and reuse them, recursion can be very efficient and run in linear time.

Interview Connect

Understanding how to spot repeated work and use memory to save time is a key skill that shows you can write smart, efficient code.

Self-Check

"What if we changed the memo array to a hash map? How would the time complexity change?"