Computing Fibonacci: Algorithms, Code, and Performance Explained

Published on 2025-03-01

Fibonacci Numbers Definition

The Fibonacci numbers are defined by the following function:

F_{n} = {\begin{matrix} 0 & if n = 0 \\ 1 & if n = 1 \\ F_{n - 1} + F_{n - 2} & if n > 1 \end{matrix}

Let's look at different ways to compute $F_{n}$ .

The Recursive Algorithm

Looking at the definition, we can see that computing $F_{n}$ for $n > 1$ can be reduced to computing $F_{n - 1}$ and $F_{n - 2}$ , then adding those two values together. Breaking down a problem into sub-problems in a recursive fashion and then combining the solutions to those sub-problems to obtain a solution to the original problem is a common techique in computer science called dynamic programming.

A straightforward way to implement such algorithm would be:

function fibRecursive(n: number): bigint {
	if (n === 0) return 0n;
	if (n === 1) return 1n;
	return fibRecursive(n - 1) + fibRecursive(n - 2);
}

Give it a try!

Complexity Analysis

Even though the algorithm does not use any explicit data structures, the fact that it is recursive means that there is an implicit data structre at play: the call stack. This stack will grow linearly with $n$ , so the space complexity of the algorithm is $O (n)$ .

Analyzing the time complexity is harder. Let's start by defining $T (n)$ as the time it takes to compute $F_{n}$ . Since computing the base cases $F_{0}$ and $F_{1}$ is done in constant time, we set:

\begin{matrix} T (0) & = 1 \\ T (1) & = 1 \end{matrix}

Now, for $n > 1$ , computing $F_{n}$ requires computing $F_{n - 1}$ which takes $T (n - 1)$ time, computing $F_{n - 2}$ which takes $T (n - 2)$ time, and then adding those solutions together which we will assume takes constant time, so we define $T (n)$ recursively as follows:

T (n) = T (n - 1) + T (n - 2) + 1

Expanding the definition a few times we get:

\begin{matrix} T (n) & = T (n - 1) + T (n - 2) + 1 \\ = 2 \cdot T (n - 2) + T (n - 3) + 2 \\ = 3 \cdot T (n - 3) + 2 \cdot T (n - 4) + 4 \\ = 5 \cdot T (n - 4) + 3 \cdot T (n - 5) + 7 \\ ⋮ \end{matrix}

A pattern seems to be emerging:

T (n) = F_{k} \cdot T (n - k + 1) + F_{k - 1} \cdot T (n - k) + (F_{k + 1} - 1)

for $k \leq n$ . Setting $k = n$ we get:

\begin{matrix} T (n) & = F_{n} \cdot T (1) + F_{n - 1} \cdot T (0) + F_{n + 1} - 1 \\ = F_{n} + F_{n - 1} + F_{n + 1} - 1 \\ = 2 \cdot F_{n + 1} - 1 \end{matrix}

Let's prove this identity by strong induction. Suppose $T (n) = 2 \cdot F_{n + 1} - 1$ for all $k \leq n$ . We first verify that the identity holds for $T (n + 1)$ :

\begin{matrix} T (n + 1) & = T (n) + T (n - 1) + 1 \\ = 2 \cdot F_{n + 1} - 1 + 2 \cdot F_{n} - 1 + 1 \\ = 2 \cdot (F_{n + 1} + F_{n}) - 1 \\ = 2 \cdot F_{n + 2} - 1 \end{matrix}

We then verify that the base cases satisfy the identity as well:

\begin{matrix} T (0) & = 2 \cdot F_{1} - 1 = 2 - 1 = 1 \\ T (1) & = 2 \cdot F_{2} - 1 = 2 - 1 = 1 \end{matrix}

Therefore, by strong induction: $T (n) = 2 \cdot F_{n + 1} - 1$ for all $n$ .

Now, from Binet's formula we have:

F_{n} = \frac{ϕ^{n} - {(- ϕ)}^{n}}{\sqrt{5}}

where $ϕ$ is the golden ratio.

As a result, the time complexity of this algorithm is $O (ϕ^{n})$ .

But we can do better! Notice that even though computing $F_{n}$ requires solving a total of $n$ unique sub-problems from computing $F_{n - 1}$ all the way down to computing $F_{0}$ , we are actually solving most of those multiple times. We can speed up the algorithm by applying a space-time trade-off: using an additional data structure to store the solutions to the problems we've already solved so that we can later retrieve them in constant time.

The Memoized Recursive Algorithm

Let's introduce an array of length $n + 1$ , where the $k^{t h}$ element in the array contains the value of $F_{k}$ we previously computed. We will name this data structure memo:

function fibMemoized(n: number, memo?: Array<bigint>): bigint {
	if (memo === undefined) {
		memo = new Array<bigint>(n + 1);
		memo[0] = 0n;
		memo[1] = 1n;
	}
	if (memo[n] === undefined) {
		memo[n] = fibMemoized(n - 1, memo) + fibMemoized(n - 2, memo);
	}
	return memo[n];
}

Give it a try!

Complexity Analysis

This time, in addition to the call stack, we also have the memo data structure, which is an array of $n + 1$ elements of $O (\log n)$ size each because of the use of BigInts to support arbitrary large integers. As such, the space complexity is $O (n \log n)$ . If we just limited the algorithm to using 64-bit integers instead, the space complexity would be $O (n)$ .

Furthermore, fibMemoized(k, memo) is called at most twice for each k from 0 to $n$ , doing $O (\log n)$ work because of the use of BigInts. As such, the time complexity is $O (n \log n)$ . If we just limited the algorithm to using 64-bit integers instead, the time complexity would be $O (n)$ .

But we can do even better! This time, lets try to improve the space complexity by getting rid of the memo data structure.

The Bottom-Up Algorithm

In the previous algorithm, we had several sub-problems that we solved in a top-down approach: we first tackled $F_{n}$ , then $F_{n - 1}$ , $F_{n - 2}$ , all the way down to $F_{1}$ and $F_{0}$ . This time, let's try to tackle the sub-problems in a bottom-up fashion:

function fibBottomUp(n: number): bigint {
	const memo = new Array<bigint>(n + 1);
	memo[0] = 0n;
	memo[1] = 1n;
	for (let k = 2; k <= n; k += 1) {
		memo[k] = memo[k - 1] + memo[k - 2];
	}
	return memo[n];
}

This algorithm has the same space and time complexities as the previous one. However, notice that to solve a sub-problem $F_{k}$ we only need the solutions to 2 other sub-problems: $F_{k - 1}$ and $F_{k - 2}$ , solutions to any earlier sub-problems are no longer needed. So we don't really need the $O (n)$ memo data structure, we just need a constant number of variables to store the two most recent solutions at each iteration:

function fibBottomUpLight(n: number): bigint {
	let a = 0n;
	let b = 1n;
	let temp: bigint;
	for (let k = 2; k <= n; k += 1) {
		temp = a;
		a = b;
		b += temp;
	}
	return b;
}

Give it a try!

Complexity Analysis

Since we got rid of the $O (n)$ memo data structure, the memory usage will get dominated by the use of BigInts, so the space complexity of the algorithm is $O (\log n)$ . If we just limited the algorithm to using 64-bit integers instead, the space complexity would be $O (1)$ .

And since we go through the for loop $n - 1$ times doing $O (\log n)$ work in each iteration because of the use of BigInts, the time complexity of the algorithm is $O (n \log n)$ . If we just limited the algorithm to using 64-bit integers instead, the time complexity would be $O (n)$ .

There is a way to improve the running-time further, but at the cost of accuracy.

The Closed-Form Approximation Algorithm

From Binet's formula we have

F_{n} = \frac{ϕ^{n} - ψ^{n}}{\sqrt{5}} = \frac{ϕ^{n}}{\sqrt{5}} - \frac{ψ^{n}}{\sqrt{5}}

where $ϕ$ is the golden ratio and $ψ = - ϕ^{- 1}$ .

Since $| \frac{ψ^{n}}{\sqrt{5}} | < \frac{1}{2}$ for all $n \geq 0$ , $F_{n}$ is the closest integer to $\frac{ϕ^{n}}{\sqrt{5}}$ , so we can compute $F_{n}$ by rounding. The problem with this approach is that $ϕ$ and $\sqrt{5}$ are irrational numbers, which means they cannot be computed exactly, regardless of how much time and memory we dedicate to the task. Therefore, the value we end up with will be an approximation of $F_{n}$ , losing accuracy as $n$ increases.

function fibClosedForm(n: number): number {
	const phi = 1.618033988749895;
	return Math.round(phi ** n / Math.sqrt(5));
}

Give it a try!

Complexity Analysis

We are not using BigInts this time, so the space complexity of the algorithm is $O (1)$ .

Furthermore, assuming constant-time mathematical operations, the time complexity of the algorithm is $O (1)$ .

Conclusion

There are several different ways to compute Fibonacci numbers, each with their own trade-offs. The recursive algorithm is easy to understand and implement as it most closely matches the mathematical definition, but it's very slow and uses quite a bit of memory. The memoized recursive algorithm is much faster but it is also memory-inefficient. The bottom-up dynamic programming approach is just as fast as the memoized recursive one, but uses a constant amount of memory. And the closed form approximation approach, while extremely fast and memory-efficient, is not very accurate.