CODEWITHSUNDEEP
recursionfibonaccitiming
afloresescarcega
afloresescarcega

Reputation: 85

Why is there a Fibonacci pattern in the timing data for a recursive Fibonacci method?

I first noticed this pattern in my class presentation over Dynamic programming vs Recursion lecture. At around the 7th Fibonacci number, the Fibonacci pattern is seen. Is there any explanation to this?

Timing data for recursive Fibonacci method The lecture presentation can be found here:

I decided to reproduce the data and noticed the pattern as well. Here is my code for my experiment:

import time

def fib(n):
    if(n <= 2):
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

for i in range(0, 100):
    start = time.time()
    print "fib(", i,") = ", fib(i), " with time: ", time.time() - start

data

Upvotes: 1

Views: 122

Answers (1)

Michael Markidis
Michael Markidis

Reputation: 4191

The reason why this is happening is due to the recursive calls within the fibonacci recurrence.

f(n) = f(n-1) + f(n-2)

Let's assume the following: 

f(n-1) takes X seconds to calculate

f(n-2) takes Y seconds to calculate. 

Therefore, f(n) will take X + Y seconds to calculate since f(n) = f(n-1) + f(n-2)

Now, if we consider the next few fibonacci numbers:

f(n+1) = f(n) + f(n-1)

f(n+1) will take X + Y seconds + X seconds = 2X + Y seconds

// f(n+2) = f(n+1) + f(n)
f(n+2) will take 2X + Y + X + Y seconds = 3X + 2Y seconds

Now, let's put in some real number to better demonstrate this.

Let's assume the following:

n = 10

f(9) takes 5 seconds to calculate

f(8) takes 3 seconds to calculate

In this case:

f(10) will take 5 + 3 = 8 seconds to calculate

f(11) will take 5 + 3 + 5 = 2(5) + 3 = 13 seconds to calculate

f(12) will take 2(5) + 3 + 5 + 3 = 3(5) + 2(3) = 21 seconds to calculate

Some other things to note:

*Times from actual runs will not always be as precise as the expected pattern. This can even be seen from your data if you look at the following output:

fib( 43 ) =  433494437  with time:  62.495429039
fib( 44 ) =  701408733  with time:  101.303709984
fib( 45 ) =  1134903170  with time:  161.135010004

161.135010004 is less than (62.495429039 + 101.303709984)

This can possibly be due fib(43) running slightly faster in the fib(45) call, then it did in the fib(44) call.

*The pattern may not be seen until you get to a certain fibonnaci number. This will depend on the precision of your time measurement. For example, if you are measuring in seconds and just going to one decimal point (i.e. 10ths of a second), then the patter will not emerge until you get passed the 0.0 second profiles.

Upvotes: 1

Related Questions