Computing runtime for the Fibonacci Sequence

Reading time ~1 minute

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.

Software Interfaces in the Wild

Interfaces are a powerful tool when used properly. This article explores a real-world example. Continue reading

Microservices are not Micro; They are Vertical

Published on October 16, 2018

Giving Life to Legacy Apps with Docker

Published on October 07, 2018