DSA Typescriptprogramming~5 mins

Why Dynamic Programming and When Recursion Alone Fails in DSA Typescript - Performance Analysis

Choose your learning style9 modes available

Time Complexity: Why Dynamic Programming and When Recursion Alone Fails

O(2^n)

Understanding Time Complexity

We want to see why simple recursion can be slow for some problems and how dynamic programming helps speed things up.

How does the number of repeated calculations affect the time it takes?

Scenario Under Consideration

Analyze the time complexity of this recursive Fibonacci function.


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

This code calculates the nth Fibonacci number using simple recursion without storing results.

Identify Repeating Operations

Look at what repeats in this code.

Primary operation: Calling fib recursively twice for each number above 1.
How many times: Many calls repeat the same fib values again and again, especially for smaller numbers.

How Execution Grows With Input

As n grows, the number of calls grows very fast because each call makes two more calls.

Pattern observation: The calls roughly double with each increase in n, causing very fast growth.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed doubles with each step up in n, making it very slow for large inputs.

Common Mistake

[X] Wrong: "Recursion always solves problems efficiently because it breaks them down."

[OK] Correct: Without remembering past results, recursion repeats the same work many times, causing slow performance.

Interview Connect

Understanding when recursion alone is slow and how dynamic programming improves it shows your skill in writing efficient code for real problems.

Self-Check

"What if we add a memory to store results (memoization)? How would the time complexity change?"