TypeScript 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 counter outside the function counts every call. Computing fib(10) = 55 takes 177 calls — for one small number. The call tree doubles at every level.

Write a TypeScript 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 call counter declared outside it on every call. Compute fib(10) and print the result and the total number of calls.

> Output: TypeScript file and captured output

Prompt

Write a TypeScript 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 call counter declared outside it on every call. Compute fib(10) and print the result and the total number of calls.

Output: TypeScript file and captured output

let calls = 0

function fib(n: number): number {
  calls++
  if (n < 2) {
    return n
  }
  return fib(n - 1) + fib(n - 2)
}

console.log("fib(10) =", fib(10))
console.log("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 TypeScript program with a recursive fib function that counts its calls in a counter declared outside it. 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: TypeScript file and captured output

Prompt

Write a TypeScript program with a recursive fib function that counts its calls in a counter declared outside it. 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: TypeScript file and captured output

let calls = 0

function fib(n: number): number {
  calls++
  if (n < 2) {
    return n
  }
  return fib(n - 1) + fib(n - 2)
}

for (const n of [5, 10, 15, 20, 25]) {
  calls = 0
  fib(n)
  const label = String(n).padStart(2)
  console.log(`fib(${label}) -> ${String(calls).padStart(7)} 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 TypeScript 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: TypeScript file and captured output

Prompt

Write a TypeScript 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: TypeScript file and captured output

const n = 25
let steps = 0

// Keep only the last two values and walk up the sequence.
let a = 0
let b = 1
for (let i = 2; i <= n; i++) {
  const next = a + b
  a = b
  b = next
  steps++
}

console.log("fib(25) =", b)
console.log("loop steps:", steps)