📈 Exponential Growth in Recursive Algorithms

Exponential growth occurs when each step multiplies the previous value by a fixed ratio:

• $a$: base (growth factor)
• $n$: input size or depth
• This is multiplicative, not additive

🌲 Recursive Trees and Exponential Time

Example: Naive Fibonacci

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

• Each call spawns 2 more calls
• Forms a binary tree of depth $n$
• Total calls ≈ $2^n$

🧪 Geometric Series in Recursive Calls

Wait a minute—recursive self-calling functions actually produce:

This is a geometric series, and its exact sum is:

🔍 Asymptotic Simplification

So it’s not exactly $a^n$—but $a^n$ is the most impactful term,
and we simplify to $a^n$ for asymptotic clarity.

As $n \to \infty$, the dominant term $a^n$ overshadows all others:

This is standard in complexity theory:

• Drop constants
• Drop lower-order terms
• Focus on growth class

🧪 Base-Specific Insight

Then I realized: for base 2, the sum is actually $2^{n+1}$,
but for base 3 onward, the sum is far from the next power—so it’s accurate to just say $a^n$.

✅ Even for $2^{n+1}$, we generalize as $2^n$ because we only care about exponential classification, not exact magnitude.

🧩 Exponential Time Without Recursion

Exponential time isn’t just about recursion—it’s about how many configurations you touch.

1. Brute-force Subset Enumeration

items = [1, 2, 3, 4, 5]
for mask in range(2**len(items)):
    subset = [items[i] for i in range(len(items)) if (mask >> i) & 1]
    evaluate(subset)

• Iterates over $2^n$ subsets
• Time complexity: $O(2^n)$

2. Brute-force String Generation

import itertools

charset = "abcde"
for attempt in itertools.product(charset, repeat=3):
    print("".join(attempt))

• Generates all strings of length $n$ from $a$ characters
• Total strings: $a^n$
• Time complexity: $O(a^n)$

3. Permutations of Input

import itertools

for perm in itertools.permutations(range(n)):
    evaluate(perm)

• Iterates over $n!$ permutations
• Time complexity: $O(n!)$ → super-exponential

4. Exhaustive Boolean Assignments

for mask in range(2**n):
    assignment = [(mask >> i) & 1 for i in range(n)]
    check_satisfiability(assignment)

• Used in SAT solvers
• Time complexity: $O(2^n)$

✅ Final Validator Summary

• Recursive trees with fixed branching grow like geometric series
• We simplify to $a^n$ because it dominates asymptotically
• Even if exact sum is $a^{n+1}$, it’s still $\Theta(a^n)$
• Exponential time can emerge from recursion or iteration over exponential spaces
• This lets us classify algorithms as exponential time