Fibonacci Using Recursion in DSA C - Time & Space Complexity

Time Complexity: Fibonacci Using Recursion

O(2^n)

Understanding Time Complexity

We want to understand how the time needed to find a Fibonacci number grows as the input number gets bigger.

How does the number of steps change when we use recursion to find Fibonacci numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int fibonacci(int n) {
    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 values until it reaches the base cases.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to fibonacci for n-1 and n-2.
• How many times: Each call generates two more calls until base cases, causing many repeated calculations.

How Execution Grows With Input

Each number requires calculating two smaller Fibonacci numbers, which themselves require two smaller ones, and so on.

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 grows very fast, roughly doubling with each increase in n.

Final Time Complexity

Time Complexity: O(2^n)

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

Common Mistake

[X] Wrong: "Since the function calls itself twice, the time complexity is just twice the input size, or O(n)."

[OK] Correct: Each call creates two more calls, leading to an exponential number of calls, not just a simple multiple.

Interview Connect

Understanding this recursive pattern helps you recognize when recursion can be inefficient and when to use better methods like memoization or iteration.

Self-Check

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