Factorial Program Algorithm Analysis

randerson112358

Sep 13, 2017·2 min read

The Factorial Algorithm is great for recursion

What is factorial ?

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example
5! = 5 x 4 x 3 x 2 x 1 = 120. It is just the product of an integer and all the integers below it.-Wikepedia

How to write a factorial function using recursion ?

The factorial program can be written recursively, because it is a function that calls itself.

Pseudo Code
1. func factorial(n)
2. if (n == 1)
3. return 1
4. return n * factorial(n -1)

C-Program

factorial(int n)
{
	//Base Case
	if(n == 1)
	return 1;
	
	return n *factorial(n-1);
}

You can see how to convert a function to recurrence relation in this video, it’s not the factorial function, but a function with the same recurrence relation.

Write the factorial function as a recurrence relation

This function written as a recurrence relation is:

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

This recurrence running time in Big O notation is: **O(n)**, which is the main purpose for converting algorithms to recurrence relations.
you can learn how to solve this from this video

Let’s look at an example:
Suppose we had a arbitrary number n=5, so we use the function factorial(5)

We get the following Number of iterations
1) factorial(5) = 5 * factorial(4)
2) factorial(4) = 4 * factorial(3)
3) factorial(3) = 3 * factorial(2)
4) factorial(2) = 2 * factorial(1)
5) factorial(1) = 1

So the factorial function called itself 5 times which is the exact same number of the input size’n’, where n = 5. So the recurrence ran ’n’ times, and is therefore O(n).

Thanks for reading this article I hope it’s helpful to you all ! Keep up the learning, and if you would like more algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for more content / videos on Algorithm Analysis and Programming:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

Resources:

1. Introduction to Algorithms, 3rd Edition
2. Wikipedia
3. Math is Fun
4. dionyziz