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.