Go 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 Go 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: Go program and captured output

Prompt

Write a Go 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: Go program and captured output

package main

import "fmt"

var calls = 0

func fib(n int) int {
  calls++
  if n < 2 {
    return n
  }
  return fib(n-1) + fib(n-2)
}

func main() {
  fmt.Println("fib(10) =", fib(10))
  fmt.Println("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 Go 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: Go program and captured output

Prompt

Write a Go 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: Go program and captured output

package main

import "fmt"

var calls = 0

func fib(n int) int {
  calls++
  if n < 2 {
    return n
  }
  return fib(n-1) + fib(n-2)
}

func main() {
  for _, n := range []int{5, 10, 15, 20, 25} {
    calls = 0
    fib(n)
    fmt.Printf("fib(%2d) -> %7d calls\n", n, 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 Go 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: Go program and captured output

Prompt

Write a Go 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: Go program and captured output

package main

import "fmt"

func main() {
  n := 25
  steps := 0

  a, b := 0, 1
  for i := 2; i <= n; i++ {
    a, b = b, a+b
    steps++
  }

  fmt.Println("fib(25) =", b)
  fmt.Println("loop steps:", steps)
}