# Computing runtime for the Fibonacci Sequence

## May 24, 2017

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.

Updated on

### Effective Microservices

I recently gave a talk at the Orlando Backend Devs Meetup on Effective Microservices. Here is the video:[Here are the slides](https://ww...… Continue reading

#### Software Interfaces in the Wild

Published on October 28, 2018

#### Microservices are not Micro; They are Vertical

Published on October 16, 2018