Fibonacci Using Recursion in DSA Typescript - Time & Space Complexity

Time Complexity: Fibonacci Using Recursion

O(2^n)

Understanding Time Complexity

We want to understand how long it takes to find a Fibonacci number using recursion.

Specifically, how the time grows as the input number gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two recursive calls for each number greater than 1.
• How many times: Each call splits into two more calls until reaching base cases.

How Execution Grows With Input

Each number requires two smaller Fibonacci calls, so the total calls grow very fast.

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

Pattern observation: The number of calls roughly doubles with each increase in n, growing exponentially.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed doubles with each increase in the input number, making it very slow for large n.

Common Mistake

[X] Wrong: "The recursive Fibonacci runs in linear time because it just counts down from n to 0."

[OK] Correct: Each call makes two more calls, so the total calls grow much faster than just counting down.

Interview Connect

Understanding this helps you see why naive recursion can be slow and why techniques like memoization improve performance.

Self-Check

"What if we add memoization to this recursive Fibonacci? How would the time complexity change?"