Introduction

Recurrence relations are one of the cleanest ways to prove that a recursive algorithm runs in exponential time. The idea is to express the running time T(n) in terms of smaller inputs, then show that the resulting recurrence grows like c^n for some constant c > 1. A classic example is the naive recursive Fibonacci algorithm.

Start with the Right Recurrence

Suppose an algorithm makes two recursive calls on inputs n - 1 and n - 2, with only constant extra work. Then its running time satisfies:

• 'T(n) = T(n - 1) + T(n - 2) + O(1)'

A direct recursive Fibonacci implementation has exactly that shape.

1def fib(n):
2    if n <= 1:
3        return n
4    return fib(n - 1) + fib(n - 2)

The runtime of this function is exponential because the recursion tree keeps branching.

Lower Bounds Are Enough to Prove Exponential Growth

To prove exponential runtime, you do not need an exact closed form immediately. A lower bound is enough.

From:

• 'T(n) = T(n - 1) + T(n - 2) + O(1)'

you get:

• 'T(n) >= T(n - 1) + T(n - 2)'

Since T(n - 1) is at least T(n - 2) for large enough n, you can derive:

• 'T(n) >= 2 * T(n - 2)'

Apply that repeatedly:

• 'T(n) >= 2 * T(n - 2)'
• 'T(n) >= 2^2 * T(n - 4)'
• 'T(n) >= 2^k * T(n - 2k)'

Choose k = n / 2 up to constants, and you get a lower bound of roughly 2^(n/2), which is exponential.

That already proves the runtime is at least exponential.

Characteristic Roots Give a Sharper Result

For recurrences such as Fibonacci's, you can go further using the characteristic equation.

Ignoring the constant term for the moment, solve:

• 'T(n) = T(n - 1) + T(n - 2)'

Assume a solution of the form r^n. Then:

• 'r^n = r^(n-1) + r^(n-2)'

Divide by r^(n-2):

• 'r^2 = r + 1'

The dominant root is the golden ratio phi, approximately 1.618. That implies the recurrence grows like phi^n, which is exponential.

This is sharper than the 2^(n/2) lower bound, but both are enough to prove exponential growth.

Exponential Does Not Require Equal-Size Subproblems

People sometimes think only recurrences like T(n) = 2T(n-1) can be exponential. That is false.

Any recurrence that creates a branching recursion tree dense enough to grow like c^n qualifies. The Fibonacci form is the classic counterexample because the subproblems are different sizes, yet the total work is still exponential.

So when analyzing recurrences, focus on total branching structure, not just symmetry.

A Contrast with Polynomial Recurrences

Compare Fibonacci-style branching with something like:

• 'T(n) = T(n/2) + O(n)'

That one is not exponential. It shrinks the problem aggressively enough that the total work stays polynomial.

The key question is whether the recursion keeps producing enough substantial subproblems to make the number of calls blow up exponentially.

How to Present the Proof Clearly

A clean proof usually has these steps:

1. write the recurrence from the code
2. simplify to a lower bound if exact analysis is unnecessary
3. unroll or compare it to a known exponential recurrence
4. conclude T(n) = Omega(c^n) for some c > 1

If you also want an upper bound, use a matching induction or characteristic-root argument. Then you can conclude Theta(c^n) instead of just Omega(c^n).

Common Pitfalls

The biggest mistake is writing the recurrence incorrectly from the code, especially forgetting extra branches.

Another mistake is trying to force the Master Theorem onto a recurrence it does not fit. Fibonacci-style recurrences are not of the standard divide-by-constant-factor form.

A third issue is proving only that the recursion tree has many nodes informally without turning that intuition into an actual bound.

Summary

• To prove exponential runtime, express the recursive algorithm as a recurrence for T(n)
• A lower bound such as T(n) >= 2 * T(n - 2) is already enough to show exponential growth
• Characteristic equations can give a sharper base, such as phi^n for Fibonacci-style recurrences
• Exponential recurrences do not need equal-size recursive calls
• A clear proof starts from the code, derives the recurrence, and then compares it to a known exponential pattern