# 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.