Answer to Question #255560 in Algorithms for Sonu

Question

1. The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

• Factorial of a non-negative integer, is multiplication of all integers smaller than or equal to n.

Write the Python program code for the above two algorithms and critically evaluate their efficiencies using Big-O notation.

Answer 1

1.

 # Function for nth Fibonacci number
 
def Fibonacci(n):
    if n<0:
        print("Incorrect input")
    # First Fibonacci number is 0
    elif n==0:
        return 0
    # Second Fibonacci number is 1
    elif n==1:
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)
 
# Driver Program
 
print(Fibonacci(n))

Algorithm makes (n-1) additions, so f(n)=O(n).

2.

# computing factorial

fact = 1
  
for i in range(1,n+1):
    fact = fact * i
      
print (fact)

Algorithm makes (n-1) multiplications, so f(n)=O(n).