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

Time Complexity: Overlapping Subproblems and Optimal Substructure

O(2^n)

Understanding Time Complexity

We want to understand how solving problems with overlapping 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 this Fibonacci function using simple recursion.

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
    

This code calculates the nth Fibonacci number by calling itself twice for smaller values.

Identify Repeating Operations

Look at the repeated calls that happen again and again.

• Primary operation: Recursive calls to fib for n-1 and n-2.
• How many times: Many calls repeat the same fib values multiple times.

How Execution Grows With Input

Each number calls two smaller numbers, doubling work roughly.

Input Size (n)	Approx. Operations
10	About 177 calls
20	Over 21,000 calls
30	More than 2 million calls

Pattern observation: The work grows very fast, almost doubling with each increase in n.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed grows very fast, doubling roughly for each step up in n.

Common Mistake

[X] Wrong: "The recursive calls only happen once each, so time is O(n)."

[OK] Correct: Actually, many calls repeat the same calculations again and again, causing exponential growth.

Interview Connect

Understanding overlapping subproblems helps you spot when to use smarter methods like memoization to save time.

Self-Check

What if we add a memory to save results already calculated? How would the time complexity change?