Calculate Total Execution time to Compute Fibonacci Sequence

An exponential big-O is represented by: O(c^n)

The n in an exponential problem means that the time of each consecutive computation of n will increase by c^n.

Recursively computing the Fibonacci sequence is a simple example of exponential big-O problems.  Let’s take a look:

package main

import "fmt"

func main() {
    fmt.Println(fib(40))
}

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

The time it would take to run (aka runtime) the operation above should be computed with O(1.6^40) and here’s why Fibonacci requires 1.6 for a constant

There are many factors that contribute to runtime with clock rate and  ISA implementation being the two most influential, but let’s say that  we are running on a system that is capable of returning a result from  the fib function every 15 nanoseconds.  Given that, it would take 15 * (1.6^40^) nanoseconds to complete this task.  This roughly equates to 2.19 seconds.

Just for fun: To exceed a million years, n would need to be greater than 104.  Here’s the calculation

Using a technique called memoization, each final computed value could  be stored in such a way that it can be referenced instead of being  computed again.  This changes the computational complexity to O(n) since each computation need not be performed more than once.

If you would like to run my code above, you can do so here.