Fibonacci's Exponential Time Complexity

The Fibonacci Sequence

The Fibonacci sequence is a famous mathematical sequence where each number is the sum of the two preceding ones. It starts with 0 and 1.

The sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

A "naive" or straightforward way to write a function to find the n-th Fibonacci number is to directly translate its definition into a recursive function:

def fib(n):



    # Base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
    



    # Recursive step
    return fib(n - 1) + fib(n - 2)

This looks simple and correct. But how does it perform? If we call fib(40), how many steps does it take? To answer this, we need to visualize the work it's doing.

Visualizing the Problem: The Recursion Tree

Just as we traced the call stack for factorial, we can trace the calls for fib. A helpful way to visualize this for a function that calls itself multiple times is to draw a recursion tree.

Let's watch a video that traces fib(4) and builds this tree structure.

The structure you just saw is the recursion tree for fib(4). Here is a static image of that same tree.

Look closely at this tree. Do you notice anything inefficient?

The most important observation is that we are doing the same work over and over again.

• fib(2) is calculated twice.
• fib(1) is calculated three times.
• fib(0) is calculated twice.

For fib(4), this might not seem so bad. But imagine calling fib(40). The number of these redundant computations grows incredibly quickly. This is the root cause of the function's poor performance.

From Tree to Time Complexity: O(2ⁿ)

Now let's quantify this growth. We need to figure out how the total number of calls (nodes in the tree) relates to the input, n.

The following segment of the video analyzes the growth of the recursion tree level by level.

As the video explained, the number of calls roughly doubles at each level of the recursion tree.

• Level 1: ~2 calls
• Level 2: ~4 calls
• Level 3: ~8 calls
• Level k: ~2ᵏ calls

The tree's depth is proportional to n. Therefore, the total number of calls is roughly on the order of 2ⁿ. In Big O notation, we say the time complexity is O(2ⁿ). This is called exponential time complexity, and it's generally considered very slow for all but the smallest inputs.

To put this in perspective:

• For n = 10, 2¹⁰ is about 1,000.
• For n = 20, 2²⁰ is about 1,000,000 (a million).
• For n = 40, 2⁴⁰ is about 1,000,000,000,000 (a trillion)!

A modern computer can't perform a trillion operations in a reasonable amount of time. This is why the naive recursive fib function becomes unusably slow for even moderate values of n.

Let's read a short text that recaps this analysis.

A More Formal Approach: Recurrence Relations

Since you have a solid math background, let's connect this visual intuition to a more formal mathematical method. We can describe the time it takes to compute fib(n) using a recurrence relation.

Let T(n) be the number of basic operations (in this case, additions) to compute fib(n).

• To compute fib(n), we must first compute fib(n-1) (which takes T(n-1) operations) and fib(n-2) (which takes T(n-2) operations).
• Then, we do one more addition to sum their results.

So, our recurrence relation is:
T(n) = T(n-1) + T(n-2) + 1

Solving this relation precisely is complex, but we can approximate it to find its Big O complexity, just as the Kantan Coding video did by assuming the tree was perfectly balanced.

The following video walks through this more formal derivation.

This confirms our visual analysis: the algorithm's runtime grows exponentially with n.

An Important Distinction: Time vs. Space Complexity

Seeing the massive O(2ⁿ) recursion tree might make you think the memory usage is also exponential. If we have a trillion function calls, do we need a trillion stack frames on the call stack?

This is a critical point of potential confusion. Let's clear it up.

To summarize the crucial insight: the call stack doesn't hold the entire tree at once.

1. The program follows one path all the way down, for example, fib(4) -> fib(3) -> fib(2) -> fib(1). The maximum depth of the stack at this point is n.
2. When fib(1) returns, its frame is popped off the stack.
3. Then, the call to fib(0) is pushed on. The stack depth doesn't grow further.
4. The entire left side of the tree for fib(n-1) is computed and its result is returned before the right side fib(n-2) is even started.

The maximum number of stack frames on the call stack at any one time is proportional to n. Therefore, the space complexity of the naive recursive Fibonacci algorithm is O(n), or linear.

This is a fantastic example of why we must analyze time and space complexity separately.

• Time Complexity: O(2ⁿ) (Exponential - very bad)
• Space Complexity: O(n) (Linear - perfectly acceptable)

Conclusion

Great job working through this analysis! It's a major step in your journey to understanding algorithms. While the fib function is a simple concept, analyzing it reveals deep truths about recursion and efficiency.

Key Takeaways:

• The naive recursive Fibonacci function has an exponential time complexity of O(2ⁿ).
• This inefficiency is caused by a massive number of redundant computations for the same subproblems, which can be visualized in a recursion tree.
• We can analyze this complexity both visually by observing the tree's growth and formally using a recurrence relation.
• Crucially, the space complexity is only linear, O(n), because the call stack's depth is limited by the longest path in the recursion tree, not the total number of nodes.

Preview of the Next Lesson:
Now that you've seen both an efficient recursive algorithm (factorial) and an inefficient one (fibonacci), we will shift our focus back to problem-solving. In the next lesson, you'll get more hands-on practice by implementing another classic recursive solution to solve a problem, such as reversing a string. This will help solidify your programming skills with recursion before we move on to more advanced topics.