Recursion lets us write the Fibonacci numbers almost exactly how the math defines them:

fib <- function(n) {
  if (n <= 1) {
    return(n)
  }
  return(fib(n-1) + fib(n-2))
}

It’s elegant, but every call spawns two more calls, and the same values get recomputed over and over.

Question: How fast does the running time grow as \(n\) increases, and can we estimate that growth rate from noisy timing data?

• Theory makes a precise prediction (next slide).
• Real runtimes are noisy: background processes, memory, caching.
• Statistics lets us estimate the growth rate and put a confidence interval on it.

Let \(C(n)\) be the number of function calls made by fib(n). Each call makes two more calls:

\[ C(n) = 1 + C(n-1) + C(n-2), \qquad C(0) = C(1) = 1 \]

Solving this recurrence gives a formula in terms of the Fibonacci numbers:

\[ C(n) = 2F_{n+1} - 1 \;\approx\; \frac{2}{\sqrt{5}}\,\varphi^{\,n+1}, \qquad \varphi = \frac{1+\sqrt{5}}{2} \approx 1.618 \]

If each call takes roughly the same time \(c\), the runtime should be

\[ T(n) \approx c \cdot \varphi^{\,n} \]

Prediction: every time \(n\) increases by 1, runtime multiplies by about \(\varphi \approx 1.618\).

Taking logs turns exponential growth into a straight line:

\[ \log T(n) = \underbrace{\log c}_{\beta_0} + \underbrace{(\log b)}_{\beta_1}\, n \]

So we fit a simple linear regression to our timing data:

\[ \log t_i = \beta_0 + \beta_1 n_i + \varepsilon_i, \qquad \varepsilon_i \sim N(0, \sigma^2) \]

• Point estimate of the growth rate: \(\hat b = e^{\hat\beta_1}\)
• 95% confidence interval for \(b\): take the interval for \(\beta_1\) and exponentiate both ends

\[ \left(e^{\,\hat\beta_1 - t^{*}\,\mathrm{SE}(\hat\beta_1)},\;\; e^{\,\hat\beta_1 + t^{*}\,\mathrm{SE}(\hat\beta_1)}\right) \]

If the theory is right, this interval should contain \(\varphi \approx 1.618\).

fib <- function(n) {
  if (n <= 1) {
    return(n)
  }
  return(fib(n-1) + fib(n-2))
}

# time each n from 20 to 28, 5 times each
n_values <- rep(20:28, each = 5)
times <- c()

for (i in 1:length(n_values)) {
  t <- system.time(fib(n_values[i]))
  times[i] <- t["elapsed"]
}

runtimes <- data.frame(n = n_values, time = times)

# regression on log(time)
model <- lm(log(time) ~ n, data = runtimes)

The runtime curve bends sharply upward. Going from \(n = 20\) to \(n = 28\) should multiply the work by about \(\varphi^{8} \approx 47\).

The points fall close to a straight line (\(R^2 = 0.995\)), confirming exponential growth. The slope of this line estimates \(\log b\).

Hover over points to see each measurement; the line is the regression model converted back to seconds.

1. The theory holds up in data. Each time \(n\) goes up by 1, runtime multiplies by about 1.613, and we’re 95% confident the true rate is between 1.596 and 1.631. The interval contains \(\varphi\), so the data agree with the recursion-tree math.
2. Logs turn exponentials into lines. Taking the log of runtime let us use ordinary linear regression, and the slope tells us how much runtime multiplies per step.
3. Statistics handles the noise. Individual timings bounce around, but repeated measurements and a confidence interval give a reliable estimate.
4. The practical lesson: naive recursion recomputes the same subproblems, so adding just one to \(n\) makes it about 62% slower.