In this post we are discussing about Explain the general plan for analyzing the efficiency of recursive algorithm Write the algorithm to find factorial of a given number Derive its efficiency
Analysis of Recursive Algorithms:-
General plan for analyzing the time efficiency of recursive algorithms
- Decide on a parameter (or parameters) indicating an input’s size.
- Identify the algorithm’s basic operation.
- 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. Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed.
- Solve the recurrence or, at least, ascertain the order of growth of its solution.
Compute the factorial function F(n) = n! for an arbitrary nonnegative integer n. Since
n! = 1 . . . . . . . .(n-1) . n = (n-1)! . n for n>=1
and 0! = 1 by definition, we can compute F (n) = F(n – 1) * n with the following recursive al Algorithm.
Algorithm
F(n)
//Computes n! recursively
//input: A nonnegative integer n
//Output: the value of n!
if n = O return I
else return F(n— l) * nSince the function F(n) is computed according to the formula
F (n) = F(n – 1) * n for n>0
Let’s analyze the efficiency of this algorithm:
- Time Complexity: The time complexity of this algorithm is O(n), where ‘n’ is the input number for which we want to find the factorial. This is because the loop runs ‘n’ times, and each iteration involves a constant amount of work (multiplication and assignment).
- Time Complexity: O(n) – The number of basic operations grows linearly with the input ‘n’.
- Space Complexity: The space complexity of this algorithm is O(1), which means it uses a constant amount of additional memory regardless of the input value ‘n’. It only requires a few extra variables (e.g., ‘factorial’ and ‘i’).
- Space Complexity: O(1) – It uses a constant amount of memory regardless of ‘n’.