Computational Complexity of Fibonacci Sequence

1. Overview

In this article, we’ll implement two common algorithms that evaluate the n^th number in a Fibonacci Sequence. We’ll then step through the process of analyzing time complexity for each algorithm.

Let’s start with a quick definition of our problem.

2. Fibonacci Sequence

The Fibonacci Sequence is an infinite sequence of positive integers, starting at 0 and 1, where each succeeding element is equal to the sum of its two preceding elements.

If we denote the number at position n as F_n, we can formally define the Fibonacci Sequence as:

F_n = o                           for n = 0
F_n = 1                            for n = 1
F_n = F_n-1 + F_n-2             for n > 1

Therefore, the start of the sequence is:

0, 1, 1, 2, 3, 5, 8, 13, …

So, how can we design an algorithm that returns the n^th number in this sequence?

3. Recursive Algorithm

Our first solution will implement recursion. This is probably the most intuitive approach, since the Fibonacci Sequence is, by definition, a recursive relation.

3.1. Method

Let’s start by defining F(n) as the function that returns the value of F_n.

To evaluate F(n) for n > 1, we can reduce our problem into two smaller problems of the same kind: F(n-1) and F(n-2). We can further reduce F(n-1) and F(n-2) to F((n-1)-1) and F((n-1)-2); and F((n-2)-1) and F((n-2)-2), respectively.

If we repeat this reduction, we’ll eventually reach our known base cases and, thereby, obtain a solution to F(n).

Employing this logic, our algorithm for F(n) will have two steps:

1. Check if n ≤ 1. If so, return n.
2. Check if n > 1. If so, call our function F with inputs n-1 and n-2, and return the sum of the two results.

Here’s a visual representation of this algorithm:

3.2. Pseudocode

Now that we understand how this algorithm works, let’s implement some pseudocode:

algorithm F(n):
    // INPUT
    //    n = Some non-negative integer
    // OUTPUT
    //    The nth number in the Fibonacci Sequence
    if n <= 1:
        return n
    else:
        return F(n - 1) + F(n - 2)

4. Analysis of Time Complexity

We can analyze the time complexity of F(n) by counting the number of times its most expensive operation will execute for n number of inputs. For this algorithm, the operation contributing the greatest runtime cost is addition.

4.1. Finding an Equation for Time Complexity

Let’s use T(n) to denote the time complexity of F(n).

The number of additions required to compute F(n-1) and F(n-2) will then be T(n-1) and T(n-2), respectively. We have one more addition to sum our results. Therefore, for n > 1:

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

When n = 0 and n = 1, no additions occur. This implies that:

T(0) = T(1) = 0

Now that we have our equation, we need to solve for T(n).

There are several ways we could do this. We’ll implement a fairly straightforward approach, where we slightly simplify T(n) and find its solution using backward substitution. The result will give us an upper bound on the time complexity of T(n).

4.2. Simplifying T(n)

Let’s start by assuming that T(n-2) ≈ T(n-1). Don’t worry about why just yet – this will become apparent shortly.

Substituting the value of T(n-1) = T(n-2) into our relation T(n), we get:

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

By doing this, we have reduced T(n) into a much simpler recurrence. As a result, we can now solve for T(n) using backward substitution.

4.3. Solving T(n) Using Backward Substitution

To do this, we first substitute T(n-1) into the right-hand side of our recurrence. Since T(n-1) = 2*T(n-2) + 1, we get:

T(n) = 2*[2*T(n-2) + 1] + 1 = 4*T(n-2) + 3

Next, we can substitute in T(n-2) = 2*T(n-3) + 1:

T(n) = 2*[2*[2*T(n-3) + 1] + 1] + 1 = 8*T(n-3) + 7

And once more for T(n-3) = 2*T(n-4) + 1:

T(n) = 2*[2*[2*[2*T(n-4) + 1]+ 1] + 1] + 1 = 16*T(n-4) + 15

We can see a pattern starting to emerge here, so let’s attempt to form a general solution for T(n). It appears to stand that:

T(n) = 2^k*T(n–k) + (2^k-1)

For any positive integer k. We can prove this equation holds through simple induction – for brevity’s sake, we’ll skip this process.

Finally, we can find k and, thereby, solve T(n), by substituting in T(0) = 1.

For T(0), we can see that n – k = 0. Rearranging, we get k = n. Now, substituting in our values for T(0) and k, we get:

T(n) = 2ⁿ*T(0) + (2ⁿ-1) = 2ⁿ + 2ⁿ – 1 = O(2ⁿ)

4.4. Analyzing Our Solution

Recall the assumption we made earlier that T(n-2) ≈ T(n-1). Since T(n-2) ≤ T(n-1) will always hold, our solution O(2ⁿ) is an upper bound for the time complexity of F(n).

It does not, however, give us the tightest upper bound. Our initial assumption removed a bit of precision. The tightest upper bound of F(n) works out to be:

T(n) = O(Φⁿ)

Where Φ = (1+√5) / 2.

Both of these solutions reveal that the run time of our algorithm will grow exponentially in n. This observation is quite intuitive if we consider that each time we call F(n), it will potentially make two more calls to F, thus doubling the cost of F(n). This is some very undesirable behavior!

5. Iterative Algorithm

Let’s move on to a much more efficient way of calculating the Fibonacci Sequence.

For this algorithm, we’ll start at our known base cases and then evaluate each succeeding value until we finally reach the n^th number. We’ll store our sequence in an array F[].

5.1. Method

First, we’ll store 0 and 1 in F[0] and F[1], respectively.

Next, we’ll iterate through array positions 2 to n-1. At each position i, we store the sum of the two preceding array values in F[i].

Finally, we return the value of F[n-1], giving us the number at position n in the sequence.

Here’s a visual representation of this process:

5.2. Pseudocode

Let’s take a look at the pseudocode for this approach:

algorithm F(n):
    // INPUT
    //    n = Some non-negative integer
    // OUTPUT
    //    The nth number in the Fibonacci Sequence
    A[0] <- 0
    A[1] <- 1
    for i <- 2 to n - 1:
        A[i] <- A[i - 1] + A[i - 2]
    return A[n - 1]

5.3. Time Complexity

Analyzing the time complexity for our iterative algorithm is a lot more straightforward than its recursive counterpart.

In this case, our most costly operation is assignment. Firstly, our assignments of F[0] and F[1] cost O(1) each. Secondly, our loop performs one assignment per iteration and executes (n-1)-2 times, costing a total of O(n-3) = O(n).

Therefore, our iterative algorithm has a time complexity of O(n) + O(1) + O(1) = O(n).

This is a marked improvement from our recursive algorithm!

6. Conclusion

In this article, we analyzed the time complexity of two different algorithms that find the n^th value in the Fibonacci Sequence. First, we implemented a recursive algorithm and discovered that its time complexity grew exponentially in n.

Next, we took an iterative approach that achieved a much better time complexity of O(n).