Analysis & Design of Algorithms

Q.2: Discuss the steps in mathematical analysis for recursive algorithm. Do the same for finding the factorial of a number.

Answer:
MATHEMATICAL ANALYSIS FOR RECURSIVE ALGORITHMS

General Plan for Analyzing the Time Efficiency of Recursive Algorithms

1. Decide on a parameter (or parameters) indicating an input's size.
2. Identify the algorithm's basic operation.
3. Check whether the number of times the basic operation is executed can vary on different
inputs of the same size; if it can, the worst-case, average-case, and best-case efficiencies
must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the number of times
the basic operation is executed.
5. Solve the recurrence or, at least, ascertain the order of growth of its solution.


Recursive Evaluation of n!

Definition: n! = 1 * 2 * ... *(n-1) * n for n 1 and 0! = 1

Recursive definition of n! :  F(n) = F(n-1)*n  for n >= 1 and F(0) = 1

*******************************

ALGORITHM F(n)

//Computes n! recursively

//Input: A nonnegative integer n

//Output: The value of n!

if n = 0 return 1

else return F(n - 1)*n

*******************************

M(n)=  M(n − 1)          +       1                  for n > 0
             to compute        to multiply
                 F(n-1)             F(n-1) by n

M(n)= M(n − 1) +1   for n>0
M(0) = 0

 

                                   M(0) = 0

the calls stop when n=0       no multiplications when n = 0

M(n-1) = M(n-2) + 1;

M(n-2) = M(n-3)+1

M(n) = [M(n-2)+1] + 1
           = M(n-2) + 2
           = [M(n-3)+1+2]
            = M(n-3) + 3
            =M(n-n) + n
            = n
Overall time Complexity: O(n)


notes For Error Please Whatsapp @9300930012