The highly inefficient fibonacci algorithm is still quite interesting.

When computing fib(n), for k less than n fib(k) is called fib(n-k) times, except when k is 0. This is called n-2 times. The total number of calls for fib(n) is

[sum (for k less than n) fib(k)]+fib(n-2)

Quick python script to check:

d={}

def fib(n):

if d.has_key(n):

d[n]=d[n]+1

else:

d[n]=1

if n==0: return 1

if n==1: return 1

return fib(n-1)+fib(n-2)

On building an integrated QuantLib/Lua platform on the world's most popular computer.

## Friday, March 19, 2010

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment