Question

Study the Fibonacci number sequence in the following two algorithmic forms: iterative (sequential) and recursive.

1) Examine the theoretical measure of complexity of each.

a) Using theory compare the number of operations and time taken to compute Fibonacci numbers recursively versus that needed to compute them iteratively.

b) How many prime Fibonacci numbers are there, and how many can you find?

c) Find the smallest Fibonacci number greater than 1,000,000 and greater than 1,000,000,000

Answer 1

1. a.

The time complexity of the iterative code is linear, as the loop runs from 2 to n, i.e. it runs in O(n) time.

For recursive series,

for n > 1:
T(n) = T(n-1) + T(n-2) + 4 (1 comparison, 2 subtractions, 1 addition)

T(n) = T(n-1) + T(n-2) + c
     = 2T(n-1) + c
     = 2*(2T(n-2) + c) + c
     = 4T(n-2) + 3c
     = 8T(n-3) + 7c
     = 2^k * T(n - k) + (2^k - 1)*c

hence, T(n) = 2^n, i.e., exponential.

For Fibonacci series in a recursive algorithm the space required is proportional to the maximum depth of the recursion tree. hence the space complexity of Fibonacci recursive is O(N).

b) There could be infinite prime fibonacci numbers. The largest known probable Fibonacci prime is F_3340367.