Question

Appreciate a step by step explanation to this question.

Write two separate programs in python that generate the n-th Fibonacci number. The programs should both take n as command line input. The first algorithm one should implement the recursive algorithm, and the second one should implement the iterative algorithm. Measure the time it takes for each of these versions (use for example, the time it module in python) to calculate the n-th Fibonacci number for the following values of n: 1, 5, 10, 15, 20, 25, 30, 35, 40, 41, 42, 43. Create a table of all your results and plot (using for example, the mat plot lib library) the time taken to compute the Fibonacci numbers using recursive and iterative algorithms, with n on the x-axis and time on the y-axis. Prove that the iterative algorithm is in quadratic time. Run the iterative algorithm and record the time on the following values of n: 2^10, 2^12, 2^14, 2^16, 2^18, 2^19 b.Plot the time of the iterative algorithm version

Answer 1

a)

# Program to display the Fibonacci sequence up to n-th term where n is provided by the user

# change this value for a different result

nterms = 10

# uncomment to take input from the user

#nterms = int(input("How many terms? "))

# first two terms

n1 = 0

n2 = 1

count = 2

# check if the number of terms is valid

if nterms <= 0:

   print("Please enter a positive integer")

elif nterms == 1:

   print("Fibonacci sequence upto",nterms,":")

   print(n1)

else:

   print("Fibonacci sequence upto",nterms,":")

   print(n1,",",n2,end=', ')

   while count < nterms:

       nth = n1 + n2

       print(nth,end=' , ')

       # update values

       n1 = n2

       n2 = nth

       count += 1

a)

def recur_fibo(n):

   """Recursive function to

   print Fibonacci sequence"""

   if n <= 1:

       return n

   else:

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

# Change this value for a different result

nterms = 10

# uncomment to take input from the user

#nterms = int(input("How many terms? "))

# check if the number of terms is valid

if nterms <= 0:

   print("Plese enter a positive integer")

else:

   print("Fibonacci sequence:")

   for i in range(nterms):

       print(recur_fibo(i))

b)

def fib (n):

    if( n == 0):

        return 0

    else:

        x = 0

        y = 1

        for i in range(1,n):

            z = (x + y)

            x = y

            y = z

            return y

for i in range(10):

    print (fib(i))