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