Optimized Fibonacci sequence

Hi everyone,

Today I’m gonna share the solution for one of the most famous programming interview problems, given a number n, write a program to get the nth element of the Fibonacci sequence.

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, … where the first two numbers are 0 and 1, and each subsequent number is the sum of the previous two.

Here there’s an obvious recursive solution:

int fibo(n)
{
    if n<=2:
        return 1;
    else:
        return fibo(n-1) + fibo(n-2);
}

it works fine for a very small n ( <= 30), but what if we need to compute the 10,000th element of the sequence?

Solution:

First of all I want to explain why the above algorithm doesn’t work for a big n, let’s illustrate how it works as a recursion tree:

let’s say we need to get the 5th element of the sequence, so we have:

fib_5

As you can see, there are a bunch of overlapping calls to fibo, actually this algorithm is O(2^n) in time complexity because to get the nth element of the sequence we need to compute all the n-1 elements and for each one we have two recursive calls… it’s just too slow!

Now, with a very small modification we can improve the efficiency of this program, it’s basically adding a “cache” table for our “already known” results, let’s take a look at the code (in Python):

#!/usr/bin/python -tt

memo = {}

def main():
    f = open("data.in","r")
    for line in f:
        print fibo(int(line))

def fibo(n):
    if n <= 2:
        return 1
    if n in memo:
        return memo.get(n)

    memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]

if __name__ == '__main__':
  main()

memo is a hashtable where we store the results for each fibo function call, so if we compute fibo(5), we don’t need to re-compute fibo(5) in the future because we already have the result in our memo table 🙂 so now we can compute fibo(10000) in just fractions of millisecond and this is because now our program runs in O(n).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s