Python Exponential Time O(2ⁿ)

When Work Doubles

O(2ⁿ) means exponential time: one extra input element doubles the work. This is the growth class where algorithms stop being usable — not for huge inputs, but already for medium ones.

Exponential work usually comes from recursion that branches: a function that calls itself twice, and each of those calls itself twice again. The calls form a tree that doubles at every level.

Recursive Fibonacci

The Fibonacci sequence starts 0, 1, and every next number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, …

The definition translates directly into a recursive function: fib(n) returns fib(n-1) + fib(n-2). It is short and correct — and exponential, because every call spawns two more, and the same values are computed again and again. fib(2) alone is recomputed thousands of times in a bigger call.

Fibonacci with recursion

A global counter counts every call. Computing fib(10) = 55 takes 177 calls — for one small number. The call tree doubles at every level.

Write a Python program with a recursive fib function (fib of n is fib of n-1 plus fib of n-2, with n below 2 returned as is) that increments a global call counter on every call. Compute fib(10) and print the result and the total number of calls.

> Output: complete Python program

Prompt

Write a Python program with a recursive fib function (fib of n is fib of n-1 plus fib of n-2, with n below 2 returned as is) that increments a global call counter on every call. Compute fib(10) and print the result and the total number of calls.

Output: complete Python program

calls = 0

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

print("fib(10) =", fib(10))
print("function calls:", calls)

Why It Explodes

Watch the call count as n grows by steps of 5. It does not grow by steps — it multiplies. Every +1 on n roughly ×1.6 on the calls; every +5 more than ×10.

At n = 50 the count would pass 40 billion calls. That is the exponential trap: the code looks innocent, and small tests finish instantly.

Count the calls as n grows

From fib(5) to fib(25) the input grows 5 times — the number of calls grows more than 16,000 times, from 15 to 242,785.

Write a Python program with a recursive fib function that counts its calls in a global counter. For n = 5, 10, 15, 20, 25 reset the counter, run fib(n), and print one aligned line per n with the call count, to show the exponential growth.

> Output: complete Python program

Prompt

Write a Python program with a recursive fib function that counts its calls in a global counter. For n = 5, 10, 15, 20, 25 reset the counter, run fib(n), and print one aligned line per n with the call count, to show the exponential growth.

Output: complete Python program

calls = 0

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

for n in [5, 10, 15, 20, 25]:
  calls = 0
  fib(n)
  print(f"fib({n:2d}) -> {calls:7d} calls")

The Fix: A Loop

The problem is not Fibonacci — it is computing the same values over and over. A loop that walks up from 0 and 1, keeping just the last two values, computes each number exactly once.

That is O(n) time and O(1) space: 24 steps instead of 242,785 calls for fib(25). Same answer, a different growth class — this is what algorithm analysis is for.

Fibonacci with a loop

Two variables walk up the sequence; each round computes one new number. fib(25) = 75025 in 24 steps — the recursive version needed 242,785 calls for the same answer.

Write a Python program that computes fib(25) with a loop instead of recursion: keep the last two values in two variables and walk up from 0 and 1, counting the loop steps. Print the result and the number of steps.

> Output: complete Python program

Prompt

Write a Python program that computes fib(25) with a loop instead of recursion: keep the last two values in two variables and walk up from 0 and 1, counting the loop steps. Print the result and the number of steps.

Output: complete Python program

n = 25
steps = 0

a, b = 0, 1
for i in range(2, n + 1):
  a, b = b, a + b
  steps += 1

print("fib(25) =", b)
print("loop steps:", steps)