Table of Content
- What is a Factorial?
- How to Solve Factorial of a Number in Python
- How to Determine the Big O Complexity of Factorial
- Wrap Off
In this lesson, you will learn about the Factorial of a number, how to solve it using loops in Python language, and calculate the big O complexity.
What is a Factorial?
The factorial of a number, most likely a non-negative integer n is the product of all positive integers, less than or equal to n.
It is denoted n followed by an exclamation point, e.g n!.
In mathematics, you should know that the factorial of 0, 0! and 1, 1! is 1. However, we are not going to get into the math behind that.
Factorial of 2, 2! = 2 * 1 = 2
Factorial of 4, 4! = 4 * 3 * 2 * 1 = 24
Factorial of 7, 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1
Let's represent the above as a function and output:
fib(2) # 2
fib(4) # 24
fib(7) # 5040
How to Solve Factorial of a Number in Python
Here is a typical problem statement for finding the factorial of a number.
Given an integer n find the factorial of that integer.
Alright, let's solve the problem together.
We will begin by defining the function named factorial in Python.
The function will have one parameter n, which denotes the non-negative integer we will find the factorial of, n!.
For example, calling the function with n equal to 2, 4, and 7 should return a Factorial similar to the example.
Now, what do we know about finding the factorial of a number? We know that the factorial of 0 and 1 is 1.
Let's create a variable called “total” and initialize it with the number, 1 since a non-negative integer begins from integer 0, whose factorial is 1.
Next, we need to find the product of all the numbers less than or equal to n, if n is greater than 1.
For that, we use a for loop that starts at 2, since multiplying by 1 has no effect.
Since we already have elements with an index equal to 0 and index equal to 1, we iterate until we have n elements in the array.
Once the for loop exits, we return the result,
Lastly, we return the result of the processing.
That is our implementation of the Factorial in Python. Let's verify by running the code.
You should get the output corresponding to each function we call.
How to Determine the Big O Complexity of Factorial
Next, we will determine the big O of the program for finding the factorial of a number in Python.
To determine the big O complexity of the function, you can either determine how many times each step is executed and then approximate the big O, as we have learned before, or you can use the rule of thumb we gave in this section as a shortcut to speed up the process.
Let's determine the big O together.
Our function contains one for loop, which repeats n times.
total = 1 runs once.
return total will also run once.
The big O will be = O(n + 1 + 1) = O(n + 2) = O(n)
From our guidelines in previous lessons, it is pretty evident that the big O complexity is linear time complexity.
So, big O is equal to O(n) as the value of n increases, the number of times line 4 executes also increases.
There you have it!
If you learned from this tutorial, or it helped you in any way, please consider sharing and subscribing to our newsletter.
Please share this post and for more insightful posts on business, technology, engineering, history, and marketing, subscribe to our newsletter.