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

Azure Kubernetes Service

I gave a talk at the 2019 Global Azure Bootcamp on Microsoft Azure's managed Kubernetes service (Azure Kubernetes Service). Here is the ...… Continue reading

Effective Microservices

Published on January 24, 2019

Software Interfaces in the Wild

Published on October 28, 2018